2
$\begingroup$

From my understanding a problem is considered to be in NP time if it can be solved in polynomial time with a non-deterministic Turing machine and verified in polynomial time with a certificate.

My question is whether or not creating an algorithm to determine values accepted by a certificate for an NP problem can itself be considered an NP problem.

This problem is an example of what I had in mind (it's more or less a variation of SAT).

Imagine a padlock with N switches and each switch has a configuration 'UP' or 'DOWN'. The padlock can have anywhere between 1 and $2^N$ solutions (i.e. it may only accept one combination or any number of combinations up to and including all possible combinations) and both the total number of solutions and the solutions themselves are selected at random.

If there are $2^N$ solutions a solution takes $O(1)$ time to find since all inputs are valid.

However, if there is only 1 solution $O(2^N)$ time is required to find it.

If it is accepted that trying all combinations on the padlock requires $2^N$ combinations and that because the solution is random there is no way to guarantee a solution unless $2^N - 1$ combinations are tested by process of elimination.

Because the total number of acceptable solutions is not known until different candidates are tested against the certificate, the problem requires $O(2^N)$ time to solve.

To prove that the problem is solvable in NP, use an NTM to solve the problem by non-deterministically testing all valid combinations and accepting any valid solution. Takes $O(N)$ time to solve since every differing possible bit to test will branch into a new non-deterministic chain.

The certificate for the problem contains acceptable values for each 'swicth' (bit) at each location either 1 for 'UP', 0 for 'DOWN' or 'X' to accept any value at that location and takes $O(N)$ time to verify.

Is this valid?

If I'm correct and the problem above does fit in the class of NP it seems sufficient to prove that $P \neq NP$ but I'm fairly confident I made an error I'm not aware of and I'm not sure if my example can be properly classed as an NP problem.

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! "if it is assumed that acceptable solutions are unknown until they are tested against the certificate" - I don't know what that means. (I don't know what "an NP problem that must naively find solutions to its own certificate" means, either.) I suggest you take a look at the definition of NP; I think that will help. We have written some reference material on the subject, here: cs.stackexchange.com/q/9556/755. Yes, if you can reduce a problem X to SAT and reduce SAT to X, then X is NP-complete. $\endgroup$ – D.W. Aug 12 '17 at 2:04
  • $\begingroup$ @D.W. Thanks! My apologies if I was unclear. What I meant is 'is a problem an NP problem if the problem has a certificate that can verify solutions in polynomial time and the solution to the problem is simply discovering what values exist on that certificate.' That's why I used the example with the lock. The lock has a valid combination (i.e. certificate) but the algorithm to solve the problem is naive to the contents of the certificate but can test solutions to see if they're valid or not. Finding the combination in such a case, assuming it's random, requires $O(2^N)$ time. $\endgroup$ – Mike Aug 12 '17 at 2:14
  • 1
    $\begingroup$ "[A] problem is considered to be in NP time if it can be solved in polynomial time with a non-deterministic Turing machine and verified in polynomial time with a certificate." There are two equivalent definitions here: "it can be solved in polynomial time with a non-deterministic Turing machine" and "[it can be] verified in polynomial time with a certificate", the latter definition missing some details. $\endgroup$ – Yuval Filmus Aug 12 '17 at 7:02
  • $\begingroup$ "If I'm correct and the problem above does fit in the class of NP it seems sufficient to prove that P≠NP...". You have a proof that your problem is EXP-hard? $\endgroup$ – rus9384 Aug 12 '17 at 8:09
  • $\begingroup$ @rus9384 Not yet. I have some ideas but they're incomplete. My first thoughts for reducing the problem in the question (let's call it P) to SAT would require that a SAT module be used to generate all possibly valid solutions for P and each solution would then be tested against P's certificate individually until one is accepted. I also have an idea to reduce P to SAT by just using a TM to discover all acceptable encodings for a SAT problem and then when input is provided it is tested to ensure it is one of those encodings. $\endgroup$ – Mike Aug 12 '17 at 9:24
3
$\begingroup$

Your problem is in the black box or oracle setting, that is, you are given access to the input as a black box rather than explicitly. You can contrast your problem with 3SAT, in which the input is a formula. One way to solve 3SAT is to try plugging in solutions at random (or systematically) and checking whether they satisfy the formula. However, better approaches are known, and these approaches use the explicit description of the formula.

The P vs NP question is in the white box setting – concretely, $\mathsf{P} \neq \mathsf{NP}$ is equivalent to the conjecture that no polynomial time algorithm solves 3SAT. Results in black box settings are irrelevant (at least directly) to the P vs NP question.

In the black box model we can also separate P from BPP (at least for promise problems), by considering the problem of finding a zero input for a balanced Boolean function. However, for explicit inputs, it is considered likely that P=BPP. This shows that the black box setting exhibits different behavior than the white box setting.

Black box settings are common in optimization, where often we are looking for algorithms which do not rely on the exact form of the input function. For example, in submodular optimization we are given a submodular function as a black box. One method for proving lower bounds in this area is the indistinguishability method, in which we construct two black boxes which are identical on most inputs but have a very different optimal solution. This method is technically much easier than similar results in the white box setting (for example, in the special case of set coverage functions or cut functions), which rely on PCP theory.

$\endgroup$
  • $\begingroup$ Thanks for the answer. Just so I'm clear on how to interpret this, is this saying the conclusion is invalid because the problem proposed is not in NP or the conclusion is invalid because only a certain class of NP problem can be used to demonstrate that $P \neq NP$? If it's the latter do you have a reference I can read so that I can understand why such a class can't be used to demonstrate $P \neq NP$ and what constraints must be satisfied for an $NP$ problem to demonstrate $P=NP$ or $P \neq NP$? $\endgroup$ – Mike Aug 17 '17 at 6:40
  • $\begingroup$ Your problem is not the kind of problem that could belong to P or to NP. It's like cats can't be used to separate P and NP. $\endgroup$ – Yuval Filmus Aug 17 '17 at 6:54
  • $\begingroup$ Rather, your problem is a black box problem - the input includes a black box. That's a different class of problems than the one of which P and NP consist. $\endgroup$ – Yuval Filmus Aug 17 '17 at 6:55
  • $\begingroup$ So in the case of the NTM described above, it's classified as a black box because solutions that would be accepted by the certificate are unknown until the machine is run? $\endgroup$ – Mike Aug 17 '17 at 7:07
  • 1
    $\begingroup$ I think I get it. The problem would require and Oracle machine to interpret whether an input is accepted by the certificate or not. As an analogy, if the problem was called 'What have I got in my pocket?' You would need to try every combination of words possible to get a correct answer, which would work and is verified immediately by a certificate, but the certificate would require an oracle machine, let's call it Bilbo, to run on the input to determine is the input is valid. Is this the right idea? $\endgroup$ – Mike Aug 17 '17 at 7:22

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.