Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Are there decision problems which are decidable but not in NP? [closed]

this is my first stackoverflow question, so be gentle. I apologize in advance if this has been beaten to death already... I read a few threads on NP but I haven't found a tantalizing answer to my question (if anything, I came up with some new ones). Briefly:

  1. Are there decision problems which are decidable but not in NP?
  2. If so, are problems which ask for a solution harder than the equivalent decision problem?

My suspicion is that the answer to the first question is a resounding 'yes' and that the answer to the second is a resounding 'no'.

In the first case, an example problem might be "given a set S, a subset T of S and a function f with domain 2^S, determine whether T maximizes f". For generic S, T and f, you can't even verify this without checking f(X) for all subsets X of S, right?

In the second case... well, I'll admit this is more of a hunch. For some reason, it doesn't seem like it should matter whether an answer contains one bit (for decision problems) or any (finite) number of bits... or, in other words, why you shouldn't be able to consider the symbols left on the tape after the TM halts as part of the "answer".

EDIT: Actually, I have a question... how precisely does your construction show that function problems are "no harder" than decision problems? If anything, you've shown that it's no easier to answer a function problem than a decision problem... which is trivial. Perhaps this is my fault for asking the question in a sloppy fashion.

Given a TM T1 in NP which solves the problem "Is X a solution to problem P" for variable X and (for the sake of argument) fixed P, is it guaranteed that there will be a TM T2 in NP which halts everywhere T1 halts, which ends in the "halt accept" state everywhere it halts, and leaves e.g. a binary representation of X on the tape?

like image 694
aegrisomnia Avatar asked Jul 15 '11 19:07

aegrisomnia


People also ask

Are all decidable problems in NP?

Note that every NP problem is decidable. This is a key concept. Remember P problems also fit the definition of NP, so…. There are certain NP-Hard problems that also exist in NP.

Do NP problems have to be decision problems?

Yes, NP is commonly only defined for decision problems In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems.

Is every decision problem decidable?

Decision problems typically appear in mathematical questions of decidability, that is, the question of the existence of an effective method to determine the existence of some object or its membership in a set; some of the most important problems in mathematics are undecidable.

Which type of problem may be NP-hard decision?

The NP problems set of problems whose solutions are hard to find but easy to verify and are solved by Non-Deterministic Machine in polynomial time. NP-Hard Problem: A Problem X is NP-Hard if there is an NP-Complete problem Y, such that Y is reducible to X in polynomial time.


1 Answers

(1) Yes, there are decision problems that are decidable but not in NP. It is a consequence of the time hierarchy theorem that NP ⊊ NEXP, so any NEXP-hard problem is not in NP. The canonical example is this problem:

Given a non-deterministic Turing machine M and an integer n written in binary, does M accept the empty string in at most n steps?

This problem is certainly decidable (just simulate all computation paths for M of length n and if see any accepts).

See this question on cstheory.stackexchange.com for many more NEXP-complete problems. And of course, there are decision problems outside NEXP: indeed, a whole exponential hierarchy of them...

(2) The answer to your second question is no: function problems are no harder than decision problems. (In a particular technical sense of "no harder than".) Suppose we have a function problem which asks for output N. Then there's a decision problem which takes an input k and asks whether the kth bit of N is 1. Solve this decision problem for every bit in the answer, and you're done!

For example, FSAT (the problem of finding a satisfying assignment to a Boolean formula) can be polynomial-time reduced to SAT (the problem of determining whether a Boolean formula has a satisfying assignment). Suppose you can solve SAT, and you are asked to find a satisfying assignment for the formula φ. Consider the first variable x in your formula φ, and ask SAT whether x∧φ is satisfiable. If it is, there must be a satisfying assignment for φ in which x is true; if not, and φ is satisfiable, then there must be a satisfying assignment for φ in which x is false. Continue with the second variable y, asking whether xy∧φ (or ¬xy∧φ, according to the answer to your first question) is satisfiable. And so on for each variable in the formula.

[I ought to add an important caveat about this example. Here SAT and FSAT are "naturally" related: they are both concerned with the same kind of thing, namely satisfying assignments to formulae. But in my argument that search in general can be reduced to decision, I used a highly artificial decision problem about the kth bit of the output. So although search reduces to decision, it doesn't necessarily reduce to the natural corresponding decision problem. In particular, Bellare and Goldwasser showed that sometimes search can't be so reduced.]

  • M. Bellare and S. Goldwasser (1994). "The complexity of decision versus search." SIAM Journal on Computing. 23:1 pp. 97–119.
like image 125
Gareth Rees Avatar answered Oct 20 '22 17:10

Gareth Rees