ABSTRACT. We study probabilistic reasoning in a context that allows for "partial truths", investigating computational and algorithmic properties of non-classical Lukasiewicz Infinitely-valued Probabilistic Logic. In particular, we study the decision problem over Lukasiewicz Infinitely-valued Probabilistic assignments which we call LIPSAT. Although the search space is initially infinite, we provide linear algebraic methods that guarantee polynomial size witnesses, so that the problem is shown to be NP-complete. An exact algorithm is presented which employs, as a subroutine, the decision problem for Lukasiewicz Infinitely-valued (Non-Probabilistic) Logic, which is also an NP-complete problem. We develop implementations of the algorithms described and discuss the empirical presence of a phase transition behavior for those problems.