FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math
P vs NP vs infinity
Post new topic   Reply to topic Page 1 of 1 [6 Posts] View previous topic :: View next topic
Author Message
Wendy E. McCaughrin
science forum beginner


Joined: 18 Jul 2005
Posts: 4

PostPosted: Fri Jul 21, 2006 2:08 am    Post subject: Re: P vs NP vs infinity Reply with quote

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 NON-deterministic machine.

: What does NP-complete 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 non-deterministic 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, NP-impossible?
: >
: > 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 co-NP, or problems that are harder than any NP problem.
: >
: > Stephen
: >
Back to top
Mitch1123
science forum beginner


Joined: 30 Nov 2005
Posts: 40

PostPosted: Fri Apr 14, 2006 2:44 pm    Post subject: Re: P vs NP vs infinity Reply with quote

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 NP-complete mean?

google mathworld np-complete?

Mitch
Back to top
William Elliot
science forum Guru


Joined: 24 Mar 2005
Posts: 1906

PostPosted: Fri Apr 14, 2006 5:42 am    Post subject: Re: P vs NP vs infinity Reply with quote

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 NP-complete 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 non-deterministic 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, NP-impossible?

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 co-NP, 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

PostPosted: Thu Apr 13, 2006 5:53 pm    Post subject: Re: P vs NP vs infinity Reply with quote

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 non-deterministic 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, NP-impossible?

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 co-NP, or problems that are harder than any NP problem.

Thanks.

Quote:

Stephen
Back to top
stephen@nomail.com
science forum Guru


Joined: 11 Sep 2005
Posts: 681

PostPosted: Thu Apr 13, 2006 5:05 pm    Post subject: Re: P vs NP vs infinity Reply with quote

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 non-deterministic 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, NP-impossible?

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 co-NP, 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

PostPosted: Thu Apr 13, 2006 4:38 pm    Post subject: P vs NP vs infinity Reply with 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?

If a problem requires infinite time, then P vs NP doesn't apply.
Is that right?

Or is infinity a special case, NP-impossible?
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [6 Posts] View previous topic :: View next topic
The time now is Wed Aug 23, 2017 10:05 am | All times are GMT
Forum index » Science and Technology » Math
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts help: proof of E(sup_n(Y_n)) < infinity Yecloud Math 9 Wed Jun 28, 2006 5:20 pm
No new posts limit(ln(x+sqrt(x^2+1)),x=-infinity) Jiri Slaby Math 33 Sat Jun 24, 2006 1:15 pm
No new posts CAS and interval computation and pseudo-values like infin... Richard J. Fateman Symbolic 10 Thu Jun 22, 2006 10:59 pm
No new posts Infinity Matlock Math 4 Tue Jun 13, 2006 8:17 am
No new posts Is Infinity A Divisor Of n? Leroy Quet Math 27 Mon Jun 12, 2006 10:29 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0431s ][ Queries: 20 (0.0185s) ][ GZIP on - Debug on ]