0
$\begingroup$

Consider the succinct versions of the P-complete problems as a Boolean circuit which represents its input in exponential more succinct ways. Could these succinct versions are in P or out of P?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Can you define your problem formally? $\endgroup$
    – Yuval Filmus
    Commented Jan 6, 2019 at 6:06
  • $\begingroup$ Have you tried reducing the computation of an arbitrary machine in some class higher than P to your problem? $\endgroup$
    – Yuval Filmus
    Commented Jan 6, 2019 at 6:06

0

Reset to default

Your Answer

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