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?

  • 2
    $\begingroup$ Can you define your problem formally? $\endgroup$ – Yuval Filmus Jan 6 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 Jan 6 at 6:06

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.