Effective Procedures and P vs NP Problem
-
05-11-2019 - |
Вопрос
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:
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.
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?
Нет правильного решения