Re: Can someone give me an example of this type of problem?

In article <1132237395.573892.65480@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<jeffrey_h_miller@xxxxxxxxx> wrote:
>Can you expound on a certficate that isn't a solution? Would "YES"
>from an algorithm that is proven to solve the problem be considered
>a short witness? What exactly is an acceptable witness?

A language L is in NP if there exists a polynomial-time Turing machine M
and a polynomial p such that

1. for all x in L there exists a string y, whose length is bounded
by p(|x|), such that M accepts the ordered pair (x,y), and

2. for all x not in L and for all strings y whose length is bounded
by p(|x|), M rejects the ordered pair (x,y).

Nothing in this definition says that y has to be a "solution"; indeed,
it is not clear how one would define precisely what a "solution" means
in the context of an arbitrary language L. For most problems that arise
in practice, it is intuitively clear what a "solution" is, but as someone
else pointed out, the case where L is the set of all primes is an example
where it is not immediately clear in what sense a primality certificate
is a "solution." Yes, you can probably make some kind of intuitive
argument that even a primality certificate is a "solution" in some kind
of intuitive sense, but at least this illustrates that it's not immediately
clear what a "solution" means in general. So, the formal definition makes
no mention of a "solution." *Any* string y can function as a certificate,
provided the conditions of the formal definition above are met.

As for your specific question, a single bit indicating 'yes' or 'no' won't
work in general as a certificate, because of condition 2; if I present M
with an ordered pair (x, yes) where x is *not* in L, M is supposed to
reject x. The 'yes' here is a lie, and so doesn't help M at all, which
is then forced to figure out on its own that it's supposed to reject x,
and this can't happen unless P = NP. So what if we try including not only
the yes/no but also the source code of the algorithm that gave the yes/no?
Then the problem is that there is no obvious way for M to accomplish its
job other than by simulating the given algorithm, which presumably takes
longer than polynomial time.

Note, however, that there is nothing "intrinsically" wrong with these
attempts at funny certificates; it's perfectly fine to include source code
or whatever you want in the certificate. Your attempts fail only because
they (presumably) don't give the right kind of information for M to do its
job, *not* because it's illegitimate to provide weird strings as putative
certificates.

The notion that a certificate can be a weird-looking string that is not
just a straightforward presentation of a "solution" is important in the
context of probabilistically checkable proofs. The so-called PCP theorem
says, roughly speaking, that NP can also be defined as the set of languages
for which there exists a short certificate that can be checked by a
randomized polynomial-time Turing machine using only a logarithmic number
of random bits and examining only a constant number of randomly chosen bits
of the certificate (as opposed to studying the whole certificate as in the
classical definition). In this case, the certificate is a very complicated
and delicately constructed object (though I suppose you can still think of
it intuitively as an error-correcting coding of a solution).

So, getting back to the original problem, it's still not clear that there
can't be a succinct certificate that encodes the necessary information in
some clever way.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: Windows 2008 CA cant issue to Windows 2003 server
    ... It is actually simpler to change the signing algorithm for the root CA, ... Issue a certificate from the root, and verify that the signature uses SHA1. ... what is the best process to decommission a Windows 2008 PKI infrastructure? ...
    (microsoft.public.windows.server.security)
  • X509 Certificates and Riijndael encryption
    ... I would like to encrypt data using AES (Rijndael) algorithm, ... as the key the key from a given certificate. ... Shouldn't I use the private key instead of the public one? ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: secrets of the EFS key pair maker
    ... > "If the certificate is not available, the private key will not be ... > and I can't find details on the algorithm that creates the key pairs. ... If you do not have the certificate and you do not have a key recovery agent ...
    (microsoft.public.windowsxp.security_admin)
  • Re: Certificate Thumbprint using Win32
    ... You should distinguish two uses of "hash value" here. ... If you are talking about the hash of the entire certificate, as done below, ... The certs panel view uses "Thumbprint algorithm" ... (signature algorithm ID). ...
    (microsoft.public.platformsdk.security)
  • Re: The message must contain a wsa:To header
    ... options I should select while going through the WSE 2 wizard. ... at ApplicationMessagingWS.Dispatch(String messageType, String ... be used along with the Integrity assertion when the presence of the ... look for a certificate with this subject name in the certificate store ...
    (microsoft.public.dotnet.framework.webservices.enhancements)