UP (complexity)

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. If P ≠ NP then either P ≠ UP or UP ≠ NP or both must be true.

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 :L = {x in {0,1}* | ∃! certificate, y with |y| = O(|x|c) such that A(x,y) = 1}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.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Complexity management — is a business methodology that deals with the analysis and optimization of complexity in enterprises. Effects of complexity pertain to all business processes along the value chain and hence complexity management requires a holistic approach.… …   Wikipedia

  • Complexity theory and organizations — Complexity theory and organizations, also called complexity strategy or complex adaptive organization, is the use of Complexity theory in the field of strategic management and organizational studies. Contents 1 Overview 2 Early research 3 Later… …   Wikipedia

  • compLexity — coL Логотип организации Страна …   Википедия

  • Complexity theory and strategy — Complexity theory has been used extensively in the field of strategic management and organizational studies, sometimes called complexity strategy or complex adaptive organization on the internet or in popular press. Broadly speaking, complexity… …   Wikipedia

  • Complexity (journal) —   Discipline Complex Systems …   Wikipedia

  • Complexity, Problem Solving, and Sustainable Societies — is a paper on energy economics by Joseph Tainter from 1996. Contents 1 Focus 1.1 Attempts 1.2 Requirement of knowledge 2 See …   Wikipedia

  • Complexity theory — may refer to: The study of a complex system or complex systems Complexity theory and organizations, the application of complexity theory to strategy Complexity economics, the application of complexity theory to economics Chaos theory, the study… …   Wikipedia

  • compLexity — Kürzel coL Manager Vereinigte Staaten Jason „1“ Lake …   Deutsch Wikipedia

  • Complexity — Com*plex i*ty, n.; pl. {Complexities}. [Cf. F. complexit[ e].] 1. The state of being complex; intricacy; entanglement. [1913 Webster] The objects of society are of the greatest possible complexity. Burke. [1913 Webster] 2. That which is complex;… …   The Collaborative International Dictionary of English

  • complexity — complexity. См. сложность генома. (Источник: «Англо русский толковый словарь генетических терминов». Арефьев В.А., Лисовенко Л.А., Москва: Изд во ВНИРО, 1995 г.) …   Молекулярная биология и генетика. Толковый словарь.

  • complexity — index complication, confusion (turmoil), enigma, entanglement (confusion), imbroglio, impasse …   Law dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”