Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Is S a NP problem?

7 views
Skip to first unread message

wij

unread,
Nov 28, 2022, 11:01:26 AM11/28/22
to
Define: bool S(Prog,Arg): S(c,n)==true iff ∃x, c(x) returns true in P-time.
S determins whether or not Proc is satisfiable in the range specifed by Arg.
Prog and Arg are pass-by-value arguments.

Ben Bacarisse

unread,
Nov 28, 2022, 11:50:37 AM11/28/22
to
This makes no sense. The "body" of S makes not reference to Arg. But
then the whole thing makes no sense because it's not phrased as a
"problem" in the theory of computation sense.

| Is S a NP problem?

Not as stated. And the messy definition hints that S is not even
decidable: for a general "program", c, it is not possible to determine
if c(x) even halts, let alone that it returns true.

--
Ben.

wij

unread,
Nov 28, 2022, 2:15:38 PM11/28/22
to
https://en.wikipedia.org/wiki/P_versus_NP_problem
..The class of questions for which an answer can be verified in polynomial time is NP,..

What is the answer (yes/no?) that a NP problem should answer when there is no certificate in P-time is available?
0 new messages