1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Avoiding the trivial certificate in complexity class NP

Discussion in 'Computer Science' started by Shuheng Zheng, Oct 8, 2018.

  1. One definition of the class NP is that there is a certificate whose size is bounded by a polynomial function of the problem instance size which can be used on a deterministic TM, along with the original input, to decide whether the input is a part of the language.

    Doesn't this definition allow the trivial loophole where we let the certificate simply be 1 if the input is a part of the language and 0 otherwise? Then the deterministic just uses the certificate entirely and totally ignores the input.

    Login To add answer/comment

Share This Page