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:
- They are similar to the Halting Problem above on the Deterministic Turing Machine with a few differences as below.
- Instead of Linear, their run-time (represented in unary) is quadratic to the input to the problem.
- 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).