Author 
Message 
mensanator@aol.compost science forum Guru
Joined: 24 Mar 2005
Posts: 826

Posted: Thu Apr 13, 2006 4:38 pm Post subject:
P vs NP vs infinity



I was discussing P vs NP with someone and since I know
just enough about the subject to always be wrong, is the
folllowing correct?
P vs NP refers to the time to _completion_.
Is that right?
If a problem requires infinite time, then P vs NP doesn't apply.
Is that right?
Or is infinity a special case, NPimpossible? 

Back to top 


stephen@nomail.com science forum Guru
Joined: 11 Sep 2005
Posts: 681

Posted: Thu Apr 13, 2006 5:05 pm Post subject:
Re: P vs NP vs infinity



mensanator@aol.compost <mensanator@aol.com> wrote:
Quote:  I was discussing P vs NP with someone and since I know
just enough about the subject to always be wrong, is the
folllowing correct?
P vs NP refers to the time to _completion_.
Is that right?

It refers to the time to solve the problem. So yes,
it refers to time to completion. Once you have produced
an answer, the "timer" stops. If you never produce
an answer, you have not solved the problem.
Quote:  If a problem requires infinite time, then P vs NP doesn't apply.
Is that right?

P and NP refer to problems that can be solved in polynomial
time, or in nondeterministic polynomial time, with respect
to the input size. "Infinite" is not polynomial with respect
to input size, deterministic or not.
Quote:  Or is infinity a special case, NPimpossible?

Infinity is not really a special case. A problem that requires
an 'infinite' amount of time is unsolvable. An unsolvable problem
is neither in P or in NP, but there is nothing special about that.
A problem that requires a finite amount of time to solve also may
not be in either P or in NP. If P<>NP then there may be solvable
problems that are neither in P or NP. For example, the problems
in coNP, or problems that are harder than any NP problem.
Stephen 

Back to top 


mensanator@aol.compost science forum Guru
Joined: 24 Mar 2005
Posts: 826

Posted: Thu Apr 13, 2006 5:53 pm Post subject:
Re: P vs NP vs infinity



stephen@nomail.com wrote:
Quote:  mensanator@aol.compost <mensanator@aol.com> wrote:
I was discussing P vs NP with someone and since I know
just enough about the subject to always be wrong, is the
folllowing correct?
P vs NP refers to the time to _completion_.
Is that right?
It refers to the time to solve the problem. So yes,
it refers to time to completion. Once you have produced
an answer, the "timer" stops. If you never produce
an answer, you have not solved the problem.
If a problem requires infinite time, then P vs NP doesn't apply.
Is that right?
P and NP refer to problems that can be solved in polynomial
time, or in nondeterministic polynomial time, with respect
to the input size. "Infinite" is not polynomial with respect
to input size, deterministic or not.
Or is infinity a special case, NPimpossible?
Infinity is not really a special case. A problem that requires
an 'infinite' amount of time is unsolvable. An unsolvable problem
is neither in P or in NP, but there is nothing special about that.
A problem that requires a finite amount of time to solve also may
not be in either P or in NP. If P<>NP then there may be solvable
problems that are neither in P or NP. For example, the problems
in coNP, or problems that are harder than any NP problem.

Thanks.


Back to top 


William Elliot science forum Guru
Joined: 24 Mar 2005
Posts: 1906

Posted: Fri Apr 14, 2006 5:42 am Post subject:
Re: P vs NP vs infinity



On Thu, 13 Apr 2006 stephen@nomail.com wrote:
Quote:  mensanator@aol.compost <mensanator@aol.com> wrote:
I was discussing P vs NP with someone and since I know
just enough about the subject to always be wrong, is the
folllowing correct?
P vs NP refers to the time to _completion_.
Is that right?
It refers to the time to solve the problem. So yes,
it refers to time to completion. Once you have produced
an answer, the "timer" stops. If you never produce
an answer, you have not solved the problem.
P means solvable in polynomial time of the lenght of input. 
NP means solvable in exponential time of the lenght of input.
What does NPcomplete mean?
Quote:  If a problem requires infinite time, then P vs NP doesn't apply.
Is that right?
P and NP refer to problems that can be solved in polynomial
time, or in nondeterministic polynomial time, with respect
to the input size. "Infinite" is not polynomial with respect
to input size, deterministic or not.
Or is infinity a special case, NPimpossible?
Infinity is not really a special case. A problem that requires
an 'infinite' amount of time is unsolvable. An unsolvable problem
is neither in P or in NP, but there is nothing special about that.
A problem that requires a finite amount of time to solve also may
not be in either P or in NP. If P<>NP then there may be solvable
problems that are neither in P or NP. For example, the problems
in coNP, or problems that are harder than any NP problem.
Stephen



Back to top 


Mitch1123 science forum beginner
Joined: 30 Nov 2005
Posts: 40

Posted: Fri Apr 14, 2006 2:44 pm Post subject:
Re: P vs NP vs infinity



William Elliot wrote:
Quote:  NP means solvable in exponential time of the lenght of input.

No, that's not right, but it is a common misconception.
Quote:  What does NPcomplete mean?

google mathworld npcomplete?
Mitch 

Back to top 


Wendy E. McCaughrin science forum beginner
Joined: 18 Jul 2005
Posts: 4

Posted: Fri Jul 21, 2006 2:08 am Post subject:
Re: P vs NP vs infinity



William Elliot <marsh@hevanet.remove.com> wrote:
: On Thu, 13 Apr 2006 stephen@nomail.com wrote:
: > mensanator@aol.compost <mensanator@aol.com> wrote:
: > > I was discussing P vs NP with someone and since I know
: > > just enough about the subject to always be wrong, is the
: > > folllowing correct?
: >
: > > P vs NP refers to the time to _completion_.
: > > Is that right?
: >
: > It refers to the time to solve the problem. So yes,
: > it refers to time to completion. Once you have produced
: > an answer, the "timer" stops. If you never produce
: > an answer, you have not solved the problem.
: >
: P means solvable in polynomial time of the lenght of input.
: NP means solvable in exponential time of the lenght of input.
No. P means: solvable by a _deterministic_ machine in polynomial time,
while the N in NP refers to NONdeterministic machine.
: What does NPcomplete mean?
: > > If a problem requires infinite time, then P vs NP doesn't apply.
: > > Is that right?
: >
: > P and NP refer to problems that can be solved in polynomial
: > time, or in nondeterministic polynomial time, with respect
: > to the input size. "Infinite" is not polynomial with respect
: > to input size, deterministic or not.
: >
: > > Or is infinity a special case, NPimpossible?
: >
: > Infinity is not really a special case. A problem that requires
: > an 'infinite' amount of time is unsolvable. An unsolvable problem
: > is neither in P or in NP, but there is nothing special about that.
: > A problem that requires a finite amount of time to solve also may
: > not be in either P or in NP. If P<>NP then there may be solvable
: > problems that are neither in P or NP. For example, the problems
: > in coNP, or problems that are harder than any NP problem.
: >
: > Stephen
: > 

Back to top 


Google


Back to top 



The time now is Mon Mar 19, 2018 7:01 am  All times are GMT

