1
$\begingroup$

According to wikipedia (https://en.wikipedia.org/wiki/P-complete):

The most basic P-complete problem is this: given a Turing machine, an input for that machine, and a number T (written in unary), does that machine halt on that input within the first T steps? It is clear that this problem is P-complete. if T is written as a unary number (a string of n ones, where n = T), then it only takes time n. By writing T in unary rather than binary, we have reduced the obvious sequential algorithm from exponential time to linear time.

Are there any natural $P-Complete$ problems such that:

  1. They are similar to the Halting Problem above on the Deterministic Turing Machine with a few differences as below.
  2. Instead of Linear, their run-time (represented in unary) is quadratic to the input to the problem.
  3. Moreover, this run-time is known to be optimum (i.e.its provable that no polynomial time algorithm can exist that runs in sub-quadratic time).
$\endgroup$
  • $\begingroup$ With some relaxed notion of 3 (whatever is implied by the time hierarchy theorem), you can use the same problem with $\sqrt{T}$ encoded in unary. $\endgroup$ – Yuval Filmus Jul 15 '17 at 10:58
  • $\begingroup$ Note also that the running time of the simulation also depends on the size of the Turing machine, so I'm not sure the simulation really runs in linear time. It is true that if you fix the Turing machine then the running time is linear. $\endgroup$ – Yuval Filmus Jul 15 '17 at 10:59
  • $\begingroup$ Unfortunately Prof. I am unable to follow you. My query is essentially that given a DTM (that represents an Algorithm $A$), the input mentioned is the input to the Algorithm/DTM (bit count of the input to be precise), and the unary number the number of steps of DTM has available for halt problem. So, is there an Algorithm (that is also $P-Complete$) which when encoded as the above problem (the optimum encoding possible) is equivalent to the original halting problem such that: The halting steps (represented in unary) are quadratic to the number of input bits. $\endgroup$ – J.Doe Jul 15 '17 at 11:12
  • 1
    $\begingroup$ The Turing machine is also part of the instance. You can fix the Turing machine to the one you consider, and then my construction should work. $\endgroup$ – Yuval Filmus Jul 15 '17 at 11:31
  • $\begingroup$ In fact linear can be replaced by any polynomial. $\endgroup$ – rus9384 Jul 16 '17 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.