UP (complexity)

Summary

• 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.

Similar Topics

• P (complexity)
• PH (complexity)
• PR (complexity)
• RP (complexity)
• FP (complexity)
• NP (complexity)
• PP (complexity)
• IP (complexity)
• R (complexity)
• L (complexity)

Related Topics

• Complexity class
• Complexity theory
• Polynomial time
• Turing machine

  * This page is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "UP (complexity)".