Please need help on promise problems

• Previous message: examachine_at_gmail.com: "Re: Cerberus and Quine"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: 27 Feb 2005 07:27:51 -0800

Hi,

When you look at a decision problem tou have :

- an input (the data of the problem)
- a question

I thought that to prove that a decision problem is in NP, one has just
to show that he can verify in polynomial time (for any input) that a
candidate is a solution (or not) to
the problem.

Now i've read that in some problems, the input satisfies a property P
and that it is NP-hard to build an instance of the problem because of
this property.

Hence some authors claims that the associated decision
problem does not likely to be in NP.

I don't understand why.

I've not seen that to prove that a decision problem is in NP, you have
also to check the propoerties of the input Hi,

If i've well understood a promise problem is a decision problem where
the input
satisfies some property P.

Now sometimes it is NP-hard to check if an input satisfies the
property P. Hence some authors claims that the associated decision
problem does not likely to be in NP.
I don't understand why. I thought that to check if a problem is in NP,
one will
just have to show that it is possible to check a solution in
polynomial time.

I've not seen that you have also to check the properties of the input.

Thanks for your help.

• Previous message: examachine_at_gmail.com: "Re: Cerberus and Quine"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]