If, suppose, P doesn't equal NP. Implication of this statement is that there is no effective procedure to solve a hard problem; however there exists an acceptable solution S. I have following two explicit queries:

  1. If an effective procedure cannot be given which yields a solution, in what sense is the S actually a solution? Does this defy the formal definition of solution? I am assuming that an effective procedure is equivalent to a proof.

  2. If there is no effective procedure to arrive at an accepted solution, this implies that solution is not a syntactic consequence of problem. According to formal definition, syntactic consequence is equivalent to an effective procedure. If solution to a hard problem is not a syntactic consequence of problem, what is it?

  • $\begingroup$ The answer to these questions seem to depend a lot on what exactly an "acceptable solution" means. Can you clarify this with a formal or intuitive definition? $\endgroup$
    – Discrete lizard
    Jan 19 '19 at 16:05
  • $\begingroup$ @Discretelizard A solution which can be checked and verified. The very property of NP (and other) problems. $\endgroup$
    – Ajax
    Jan 19 '19 at 16:33
  • $\begingroup$ Ah, so you mean a solution for a specific instance of the problem. In that case, the answer given should cover things. $\endgroup$
    – Discrete lizard
    Jan 19 '19 at 16:44

No. $\mathrm{P}\neq\mathrm{NP}$ means that there is no efficient (i.e., deterministic polynomial time) solution to $\mathrm{NP}$-hard problems, not that there is no effective (i.e., computable) solution. The fact that the solution is hard to find doesn't mean that it's impossible to find. Indeed, essentially the whole reason that $\mathrm{NP}$ is an interesting class of problems is that we know how to check proposed solutions to $\mathrm{NP}$ efficiently. Regardless of how hard it is to find satisfying assignments to Boolean formulas, if I give you an assignment and tell you that it satisfies the formula, you can easily check that I'm telling the truth.

  • $\begingroup$ Is there a clear segregation (with examples) between efficient (deterministic polynomial time) and effective procedures? $\endgroup$
    – Ajax
    Jan 19 '19 at 16:35
  • 1
    $\begingroup$ Yes. The time hierarchy theorem says that there are problems that can be solved in deterministic exponential time (e.g., any $\mathrm{EXP}$-complete problem) but which aren't in $\mathrm{P}$. I think you need to read up on the basics of computability and complexity theory, here. $\endgroup$ Jan 19 '19 at 16:37

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.