I assume you mean in the sense that deciding satisfiability of arbitrary propositions (over uncertain variables; certainly true/false ones can be simplified out) is NP-complete. Of course I mean that a variable v is uncertain if 0<p(v)<1.
Actually, solving SAT problems is just the simplest case. Even so, if you have only certain variables (with either 0 or 1 plausibility), it’s still NP-complete, you can’t just simplify them in polynomial time. [EDIT: This is wrong as Jonathan pointed it out.]
In extreme case, since we also have the rule that “robot” has to use all the available information to the fullest extent, it means that the “robot” must be insanely powerful. For example if the calculation of some plausibility value depends for example the correctness of an algorithm (known by the “robot”, with a very high probability), then it will have to be able to solve the halting problem in general.
Even if you constrain your probability values to be never certain or impossible, you can always chose small (or large) enough values, so that the computation of the probabilities can be used to solve the discrete version of the problem.
For example, in the simplest case: if you just have a set of propositions in (let us say in conjunctive normal form), the consistency desideratum implies the ability of the “robot” to solve SAT problems, even if the starting plausibility values for the literals fall into the open (0,1) interval.
I think you misunderstood. The robot has a real number p(v) for every v. Let’s grant an absolute min and max of 0 and 1. My point was simply that when p(v)=0 or p(v)=1, v can be simplified out of propositions using it.
I understand why computing the probability of a proposition implies answering whether it’s satisfiable.
I assume you mean in the sense that deciding satisfiability of arbitrary propositions (over uncertain variables; certainly true/false ones can be simplified out) is NP-complete. Of course I mean that a variable v is uncertain if 0<p(v)<1.
Actually, solving SAT problems is just the simplest case. Even so, if you have only certain variables (with either 0 or 1 plausibility), it’s still NP-complete, you can’t just simplify them in polynomial time. [EDIT: This is wrong as Jonathan pointed it out.]
In extreme case, since we also have the rule that “robot” has to use all the available information to the fullest extent, it means that the “robot” must be insanely powerful. For example if the calculation of some plausibility value depends for example the correctness of an algorithm (known by the “robot”, with a very high probability), then it will have to be able to solve the halting problem in general.
Even if you constrain your probability values to be never certain or impossible, you can always chose small (or large) enough values, so that the computation of the probabilities can be used to solve the discrete version of the problem.
For example, in the simplest case: if you just have a set of propositions in (let us say in conjunctive normal form), the consistency desideratum implies the ability of the “robot” to solve SAT problems, even if the starting plausibility values for the literals fall into the open (0,1) interval.
I think you misunderstood. The robot has a real number p(v) for every v. Let’s grant an absolute min and max of 0 and 1. My point was simply that when p(v)=0 or p(v)=1, v can be simplified out of propositions using it.
I understand why computing the probability of a proposition implies answering whether it’s satisfiable.
Sorry for the confusion. I was very superficial. Of course, your are correct about being able to simplify out those values.