Search   Memberlist   Usergroups
 Page 1 of 1 [6 Posts]
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, NP-impossible?
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 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
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 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
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 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
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 NP-complete mean?

Mitch
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 wrote: : On Thu, 13 Apr 2006 stephen@nomail.com wrote: : > mensanator@aol.compost 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 : >

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [6 Posts]
 The time now is Mon Feb 18, 2019 8:25 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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