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!

$\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, 2023 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$ Mar 8, 2023 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, 2023 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, 2023 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$ Mar 9, 2023 at 11:44

1 Answer 1

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.

$\endgroup$

Your Answer

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

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