Meta tags:

Headings (most frequently used words):

contents, relation, to, decision, problems, related, complexity, classes, formal, definitions, history, see, also, references, external, links,

Text of the page (most frequently used words):
the (49), displaystyle (20), complexity (17), polynomial (15), that (15), for (14), problem (14), #problems (14), there (12), class (11), complete (11), edit (11), are (11), this (9), time (9), classes (8), decision (8), any (8), wikipedia (7), and (6), with (6), hierarchy (6), given (6), such (6), how (6), many (6), page (5), number (5), from (5), all (5), set (5), machine (5), can (5), than (5), contents (4), search (4), links (4), pdf (4), permanent (4), see (4), exists (4), epsilon (4), defined (4), article (4), history (4), big (4), mathbb (4), whether (4), easy (4), hide (4), move (4), sidebar (4), add (3), view (3), terms (3), was (3), list (3), proof (3), other (3), computing (3), computer (3), computational (3), counting (3), relation (3), also (3), which (3), instance (3), algorithm (3), computation (3), turing (3), asks (3), graph (3), more (3), most (3), example (3), count (3), zero (3), related (3), satisfy (3), function (3), form (3), tools (3), main (3), languages (2), toggle (2), table (2), contact (2), about (2), privacy (2), policy (2), using (2), use (2), short (2), description (2), wikidata (2), title (2), checkable (2), boolean (2), exptime (2), considered (2), infeasible (2), pspace (2), hard (2), external (2), stockmeyer (2), larry (2), 2009 (2), doi (2), leslie (2), valiant (2), 1979 (2), science (2), university (2), barak (2), boaz (2), references (2), theory (2), portal (2), proved (2), every (2), oracle (2), sat (2), hash (2), leq (2), functions (2), equals (2), size (2), certificates (2), checked (2), correctness (2), ask (2), follows (2), accepting (2), nondeterministic (2), formally (2), formal (2), definitions (2), paths (2), significant (2), bit (2), answer (2), pronounced (2), least (2), some (2), difficult (2), information (2), one (2), solve (2), must (2), corresponding (2), answers (2), root (2), roots (2), univariate (2), real (2), positive (2), variable (2), assignments (2), cnf (2), formula (2), hamiltonian (2), cycles (2), have (2), cost (2), less (2), 100 (2), subsets (2), integers (2), appearance (2), upload (2), file (2), changes (2), read (2), log (2), create (2), account (2), donate (2), menu (2), topic, mobile, cookie, statement, statistics, developers, code, conduct, legal, safety, contacts, disclaimers, text, available, under, additional, may, apply, site, you, agree, registered, trademark, non, profit, organization, wikimedia, foundation, inc, creative, commons, attribution, sharealike, license, rendered, parsoid, last, edited, august, 2026, utc, hidden, categories, restricted, titles, leading, sign, mdy, dates, january, 2025, different, articles, category, retrieved, https, org, index, php, oldid, 1369983685, interactive, system, probabilistically, nspace, dspace, ntime, dtime, families, arithmetical, grzegorczyk, exponential, hierarchies, polyl, nonelementary, elementary, expspace, nexptime, qma, fnp, tfnp, suspected, apx, bqp, bpp, zpp, reg, acc, dlogtime, feasible, zoo, november, 1985, 861, archived, october, original, 1137, 0214060, 849, siam, journal, approximation, algorithms, 201, 1016, 0304, 3975, 90044, 189, elsevier, theoretical, cambridge, press, 344, 978, 521, 42426, isbn, modern, approach, arora, sanjeev, spring, 2006, princeton, 522, quantum, computability, programming, has, returns, high, probability, runtime, based, leftover, lemma, randomized, first, square, matrix, called, verifier, words, containing, deterministic, equivalently, verifer, membership, input, questions, exist, context, certificate, branches, closest, majority, half, accept, finds, parity, instead, surprisingly, believed, correspond, linear, consequence, entire, fact, only, needs, make, query, indication, extreme, difficulty, solving, exactly, toda, theorem, clearly, then, tell, just, them, greater, these, enough, while, others, rather, does, finding, satisfiability, conjunctive, normal, traveling, salesman, subset, sum, often, stated, solutions, certain, constraints, sharp, sometimes, associated, compute, where, running, unlike, well, known, not, but, representative, correct, substitution, due, technical, restrictions, free, encyclopedia, item, projects, printable, version, download, print, export, switch, legacy, parser, get, shortened, url, cite, link, what, here, general, actions, english, talk, русский, português, 한국어, 日本語, italiano, עברית, français, español, deutsch, català, العربية, top, personal, special, pages, recent, community, learn, help, contribute, random, current, events, navigation, jump, content,

Text of the page (random words):
p wikipedia jump to content main menu main menu move to sidebar hide navigation main page contents current events random article about wikipedia contact us contribute help learn to edit community portal recent changes upload file special pages search search appearance donate create account log in personal tools donate create account log in contents move to sidebar hide top 1 relation to decision problems 2 related complexity classes 3 formal definitions 4 history 5 see also 6 references 7 external links toggle the table of contents p 12 languages العربية català deutsch español français עברית italiano 日本語 한국어 português русский 中文 edit links article talk english read edit view history tools tools move to sidebar hide actions read edit view history general what links here related changes upload file permanent link page information cite this page get shortened url switch to legacy parser print export download as pdf printable version in other projects wikidata item appearance move to sidebar hide from wikipedia the free encyclopedia complexity class the correct title of this article is p the substitution of the is due to technical restrictions in computational complexity theory the complexity class p pronounced sharp p or sometimes number p or hash p is the set of the counting problems associated with the decision problems in the set np more formally p is the class of function problems of the form compute f x where f is the number of accepting paths of a nondeterministic turing machine running in polynomial time unlike most well known complexity classes it is not a class of decision problems but a class of function problems the most difficult representative problems of this class are p complete relation to decision problems edit an np decision problem can often be stated in the form are there any solutions that satisfy certain constraints for example are there any subsets of a list of integers that add up to zero subset sum problem are there any hamiltonian cycles in a given graph with cost less than 100 traveling salesman problem are there any variable assignments that satisfy a given cnf conjunctive normal form formula boolean satisfiability problem or sat does a univariate real polynomial have any positive roots root finding corresponding p function problems ask how many rather than are there any for example how many subsets of a list of integers add up to zero how many hamiltonian cycles in a given graph have cost less than 100 how many variable assignments satisfy a given cnf formula how many roots of a univariate real polynomial are positive related complexity classes edit clearly a p problem must be at least as hard as the corresponding np problem if it s easy to count answers then it must be easy to tell whether there are any answers just count them and see whether the count is greater than zero some of these problems such as root counting are easy enough to be in fp while others are p complete one consequence of toda s theorem is that a polynomial time machine with a p oracle p p can solve all problems in ph the entire polynomial hierarchy in fact the polynomial time machine only needs to make one p query to solve any problem in ph this is an indication of the extreme difficulty of solving p complete problems exactly surprisingly some p problems that are believed to be difficult correspond to easy for example linear time p problems for more information on this see p complete the closest decision problem class to p is pp which asks whether a majority more than half of the computation paths accept this finds the most significant bit in the p problem answer the decision problem class p pronounced parity p instead asks for the least significant bit of the p answer formal definitions edit p is formally defined as follows p is the set of all functions f 0 1 n displaystyle f 0 1 to mathbb n such that there is a polynomial time nondeterministic turing machine m displaystyle m such that for all x 0 1 displaystyle x in 0 1 f x displaystyle f x equals the number of accepting branches in m displaystyle m s computation graph on x displaystyle x 1 p can also be equivalently defined in terms of a verifer a decision problem is in np if there exists a polynomial time checkable certificate to a given problem instance that is np asks whether there exists a proof of membership for the input that can be checked for correctness in polynomial time questions in p ask how many certificates there exist for a problem instance that can be checked for correctness in polynomial time 1 in this context p is defined as follows p is the set of functions f 0 1 n displaystyle f 0 1 to mathbb n such that there exists a polynomial p n n displaystyle p mathbb n to mathbb n and a polynomial time deterministic turing machine v displaystyle v called the verifier such that for every x 0 1 displaystyle x in 0 1 f x y 0 1 p x v x y 1 displaystyle f x big big y in 0 1 p x v x y 1 big big 2 in other words f x displaystyle f x equals the size of the set containing all of the polynomial size certificates history edit the complexity class p was first defined by leslie valiant in a 1979 article on the computation of the permanent of a square matrix in which he proved that permanent is p complete 3 larry stockmeyer has proved that for every p problem p displaystyle p there exists a randomized algorithm using an oracle for sat which given an instance a displaystyle a of p displaystyle p and ϵ 0 displaystyle epsilon 0 returns with high probability a number x displaystyle x such that 1 ϵ p a x 1 ϵ p a displaystyle 1 epsilon p a leq x leq 1 epsilon p a 4 the runtime of the algorithm is polynomial in a displaystyle a and 1 ϵ displaystyle 1 epsilon the algorithm is based on the leftover hash lemma see also edit computer programming portal quantum computing relation to computability and complexity theory references edit 1 2 barak boaz spring 2006 complexity of counting pdf computer science 522 computational complexity princeton university arora sanjeev barak boaz 2009 computational complexity a modern approach cambridge university press p 344 isbn 978 0 521 42426 4 leslie g valiant 1979 the complexity of computing the permanent theoretical computer science 8 2 elsevier 189 201 doi 10 1016 0304 3975 79 90044 6 stockmeyer larry november 1985 on approximation algorithms for p pdf siam journal on computing 14 4 849 861 doi 10 1137 0214060 archived from the original pdf on october 28 2009 external links edit complexity zoo class p v t e complexity classes considered feasible dlogtime ac 0 acc 0 reg tc tc 0 l sl rl fl nl nl complete nc sc cc p p complete zpp rp bpp bqp apx fp suspected infeasible up np np complete np hard co np co np complete tfnp fnp am qma ph p pp p p complete ip pspace pspace complete considered infeasible exptime nexptime expspace 2 exptime elementary nonelementary pr r re all other complexity classes polyl qp class hierarchies polynomial hierarchy exponential hierarchy grzegorczyk hierarchy arithmetical hierarchy boolean hierarchy families of classes dtime ntime dspace nspace probabilistically checkable proof interactive proof system list of complexity classes retrieved from https en wikipedia org w index php title p oldid 1369983685 category complexity classes hidden categories articles with short description short description is different from wikidata use mdy dates from january 2025 restricted titles leading number sign this page was last edited on 18 august 2026 at 11 50 utc page was rendered with parsoid text is available under the creative commons attribution sharealike 4 0 license additional terms may apply by using this site you agree to the terms of use and privacy policy wikipedia is a registered trademark of the wikimedia foundation inc a non profit organization privacy policy about wikipedia disclaimers contact wikipedia legal safety contacts code of conduct developers statistics cookie statement mobile view search search toggle the table of contents p 12 languages add topic