2
$\begingroup$

My friend and I were studying NP-hard problems and NP-completeness. I don't think we have understood the concept very well so I thought I would come here to solve our doubt.

To show that a given problem is in NP, we have to verify a solution to a given instance of the problem can be solved in polynomial time. We get this. What we wanted to know is that is by default then every existing problem is in NP until a solution for the problem is derived in polynomial time? Or is it that we have completely missed the concept?

$\endgroup$
4
$\begingroup$

There are plenty of problems where there is likely no way to verify a solution in polynomial time.

Amazingly, the problem "is p a prime number" is in NP due to some deep mathematical theorem that shows that for every prime number, there is a polynomial time proof that it is a prime number. (For many, many NP complete problems the part that there is a polynomial time proof is quite trivial).

A simple problem: Given an integer n, how many prime numbers p <= n are there? There are ways to calculate this in $O(n^{2/3})$ and possibly a bit faster (which is exponential in the problem size). But there seems to be no possible proof that is less time consuming then finding the solution from scratch. so no proof that doesn't take exponential time.

Here's a simple problem that I believe has an absurdly high time complexity: On the UK TV show "Countdown", the contestants are given six slightly random numbers, and another larger number, and are asked to form the larger number by combining any or all of the six random numbers using + - * and /. That's the simplest problem. The next, harder problem: Given six integers and some larger n, can all integers 1 ≤ i ≤ n be formed that way? The next, harder problem: Given n, are there six numbers a1 to a6 so that all integers ≤ n can be formed by combing a1 to a6?

And the final problem (as a decision problem): Given an integer k ≥ 1, and a larger integer n ≥ 1, are there k integers $a_1$ to $a_k$ such that all integers 1 ≤ k ≤ n can be formed by combining any or all of $a_1$ to $a_k$ using +, -, *, / ?

$\endgroup$
  • $\begingroup$ The problem "is $p$ a prime number" is even in P. $\endgroup$ – Yuval Filmus May 6 '18 at 22:02
  • $\begingroup$ You are of course right. What I find amazing is that it requires quite deep mathematics to prove it is even in NP (but it's trivial in co-NP), where many NP-complete problems like Travelling Salesman are quite trivial in NP. $\endgroup$ – gnasher729 May 7 '18 at 14:17
  • $\begingroup$ I'm unsure about your "hard countdown" example. If you can use a1,..,a6 only once, you get produce only a bounded amount of numbers, so once n is large enough the answer is "no", and the problem is O(1). If you can use them more than once, you can take a1=1 and use 1+1+1+... to answer "yes" in all cases, solving it in O(1). Am I missing something? (+1) $\endgroup$ – chi May 7 '18 at 20:46
  • $\begingroup$ Checking if all 1 <= i <= n can be produced is just n times harder than checking only n. The hard problem is finding one set of 6 numbers that allows constructing the largest possible number of consecutive numbers. The number of choices for a1 to ak is huge. Picking 7 numbers is much much harder, and so on. $\endgroup$ – gnasher729 May 7 '18 at 23:57
3
$\begingroup$

By the time hierarchy theorem, there are problems in NEXPTIME and EXPSPACE which are not in NP.

One famous example of a problem which is not in NP is deciding whether two regular expressions represent the same language. If the regular expressions are built from union, concatenation, and squaring, then the problem is NEXPTIME-complete. If we add Kleene star, the problem is EXPSPACE-complete. Either way, the problem is not in NP.

A large and important class of problems which are generally not in NP is the class of satsifiability modulo theories (SMT) decision problems.

Take, for example, Presburger arithmetic, which is the theory of natural numbers with addition. This is known to be decidable. (Adding multiplication gives you Peano arithmetic, which Gödel showed was not decidable.)

This is a problem that is built on top of boolean logic, in the sense that statements in Presburger arithmetic are statements in logic where some of those statements are statements about natural numbers.

So the decision problem for Presburger arithmetic includes SAT as a subproblem. SAT is NP-hard, so we might expect the Presburger arithmetic problem to be more complex than that. And, indeed, it is known to be in 2EXPTIME and not in NP.

It's a similar story with the decision problem for real closed fields.

$\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.