Group Members:
Similar Artists:
Formal Connection With:
- Genres: Rock
- Representative Albums: "Killer Up
| Artist: The Up |
Group Members:
Similar Artists:
Formal Connection With:
| Discography: The Up |
| Wikipedia: UP (complexity) |
In complexity theory, UP ("Unambiguous Non-deterministic Polynomial-time") is the complexity class of decision problems solvable in polynomial time on a non-deterministic Turing machine with at most one accepting path for each input. UP contains P and is contained in NP.
A common reformulation of NP states that a language is in NP if and only if a given answer can be verified by a deterministic machine in polynomial time. Similarly, a language is in UP if a given answer can be verified in polynomial time, and the verifier machine only accepts at most one answer for each problem instance. More formally, a language L belongs to UP if there exists a two input polynomial time algorithm A and a constant c such that
Algorithm A verifies L in polynomial time.
UP (and its complement co-UP) contain the integer factorization problem; because determined effort has yet to find a polynomial-time solution to this problem, it is suspected to be difficult to show P=UP, or even P=(UP ∩ co-UP).
The famous Valiant-Vazirani theorem states that NP is contained in RPPromise-UP, which means that there is a randomized reduction from any problem in NP to a problem in Promise-UP.
UP is not known to have any complete problems.[1]
|
||||||||||||||
This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)
| Johnsen, William H. (Quotes By) | |
| volute | |
| up (Idiom) |
| How do you get it up? Read answer... | |
| What is what's up? Read answer... | |
| What is the UPS? Read answer... |
| What does what up? | |
| Not on the up and up? | |
| Are you a up? |
Copyrights:
![]() | Artist. Copyright © 2009 All Media Guide, LLC. Content provided by All Music Guide ®, a trademark of All Media Guide, LLC. All rights reserved. Read more | |
![]() | Wikipedia. This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article "UP (complexity)". Read more |
Mentioned in