1
$\begingroup$

Complexity class P/poly includes languages, which cannot be calculated by means of classic Turing machine, including unary halting problem
However, class NP is relatively simple, can be calculated via Turing machine and is placed on lowest level in polynomial hierarhy

So every NP-complete problem, which can be represented as NP-language recognition, can be easily turned into P/poly class:
Step 1: Make Turing maching which recognises apropriate NP-complete language. If language is not inside NP, perform force stuck in infinite loop
Step 2: Make unary representation of that turing machine
Step 3: Solve halting problem for this machine via boolean circuit, that lies in P/poly class
Step 4: If machine halts, original language is NP-language, that had been proved in P/poly-wide scope. So, NP lies in P/poly

Where is my misunderstooding? Thanks!

Improve this question
$\endgroup$
7
  • $\begingroup$ "Complexity class P includes languages, which cannot be calculated by means of classic Turing machine, including unary halting problem." Why do you say this problem is in P? $\endgroup$
    – kviiri
    Mar 8 at 14:45
  • 1
    $\begingroup$ @kviiri I review my question several times and don't see any mention of class P there, but if any, it should be P/poly (en.m.wikipedia.org/wiki/P/poly ), which is class of boolean circuits with polynomial size $\endgroup$
    – Vladislav Ihost
    Mar 8 at 15:22
  • $\begingroup$ I don't understand what "Solve halting problem for this machine via boolean circuit, that lies in P/poly class" means exactly, or why you think it is possible to solve the halting problem in P/poly. I think you need to elaborate on this step. $\endgroup$
    – D.W. ♦
    Mar 9 at 6:21
  • $\begingroup$ "If machine halts, original language is NP-language" - I don't understand what you mean exactly, nor how it is relevant. You seem to be confusing a NP language vs an element of that language. Also, conversion to unary could cause an exponential increase in running time which your argument needs to address. $\endgroup$
    – D.W. ♦
    Mar 9 at 6:22
  • $\begingroup$ @D.W. About unary halting problem. Several sources claims that unary halting problem (UHALT) lies in P/poly. For instance, there are two proofs: (iccl.inf.tu-dresden.de/w/images/e/eb/… , slide 19 ) and ( mathoverflow.net/a/57242 ) As I can understood, belonging UHALT to P/poly class is well-known fact and is not conditional result (Like results that uses Karp-Lipton theorem) $\endgroup$
    – Vladislav Ihost
    Mar 9 at 11:44

1 Answer 1

Reset to default
3
$\begingroup$

The problem is that you have to transform the input for the original machine into a unary input for the unary machine. This cannot be done in polynomial time in the size of the original input, therefore your proposed algorithm is not a $\mathsf{P/poly}$ algorithm.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.