0
$\begingroup$

I have noticed that whenever the scope of a problem is pushed to infinity, problems in NP have an uncountably infinite decision space whereas problems in P seem to have a countably infinite decision space. I'm curious if this is always true, and if there is any value to this observation.

Consider a case of 3-sat (which is NP complete) in which there are countably infinite variables to assign values to. There are uncountably infinitely many assignments to variables because an assignment corresponds to an infinite length binary string. The decision space in this case in uncountably infinite. Knapsack is clearly the same - consider a case with an infinite number of items. Which items are chosen corresponds to an infinite length binary string.

Consider the problem of finding the greatest common factor of two numbers x and y (a problem known to be solvable in polynomial time). As x and y both are pushed to infinity, it is not hard to see that the set of possible solutions as we approach this limit becomes countably infinite.

$\endgroup$
  • $\begingroup$ And your question is? $\endgroup$ – Asaf Karagila Apr 17 '15 at 20:58
  • $\begingroup$ @Asaf The question: "I'm curious if this is always true, and if there is any value to this observation." $\endgroup$ – Steve Apr 17 '15 at 21:36
  • $\begingroup$ Mahaney's Theorem might be the insight that you're struggling toward, otherwise this question makes no sense to me. $\endgroup$ – Kyle Jones Apr 18 '15 at 1:20
0
$\begingroup$

Consider sorting. It runs in polynomial time, yet chooses one correct answer from $n!$ possibilities. This is greater than the potentially $2^n$ possibilities for the SAT problem over $n$ variables, for example. So if I understand the outlines of your argument, this would be a counterexample.

$\endgroup$
0
$\begingroup$

2SAT is in P, yet whatever you said about 3SAT holds also for 2SAT.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.