Meta tags:
Headings (most frequently used words):
complexity, problems, classes, machine, and, problem, np, computational, theory, models, measures, important, on, instances, the, of, other, in, contents, open, intractability, continuous, history, see, also, works, references, external, links, representing, decision, as, formal, languages, function, measuring, size, an, instance, turing, best, worst, average, case, upper, lower, bounds, defining, hierarchy, theorems, reduction, versus, not, known, to, be, or, complete, separations, between, citations, textbooks, surveys,
Text of the page (most frequently used words):
the (356), #complexity (162), displaystyle (155), problem (121), and (107), time (88), #problems (87), that (84), computational (75), for (64), are (62), theory (61), textsf (61), turing (49), this (48), can (47), algorithm (43), classes (43), machine (41), not (37), edit (35), with (29), complete (25), decision (24), polynomial (24), known (24), deterministic (24), computer (23), algorithms (23), input (23), log (23), mathematical (22), hierarchy (22), set (21), computing (21), machines (21), space (21), such (21), instance (21), analysis (20), most (20), one (19), used (19), other (18), mathematics (18), computation (18), size (18), all (18), case (18), from (17), model (17), class (17), which (17), software (16), solve (16), solved (16), many (16), poly (16), non (15), science (15), graph (15), any (15), defined (15), information (14), important (14), these (14), resources (14), more (14), language (13), pspace (13), instances (13), but (13), since (13), models (13), function (12), than (12), some (12), hard (11), has (11), doi (11), 978 (11), isbn (11), however (11), example (11), would (11), solution (11), there (11), integer (11), best (11), big (11), text (10), using (10), number (10), worst (10), average (10), have (10), two (10), given (10), reduction (10), about (9), may (9), different (9), operations (9), list (9), continuous (9), see (9), measures (9), thus (9), equal (9), yes (9), possible (9), particular (9), inputs (9), large (8), systems (8), general (8), network (8), system (8), formal (8), theoretical (8), dtime (8), bpp (8), pdf (8), 2006 (8), isomorphism (8), also (8), each (8), its (8), theorem (8), theorems (8), same (8), then (8), whether (8), answer (8), main (8), reductions (8), lower (8), toggle (7), wikipedia (7), discrete (7), measure (7), field (7), quantum (7), security (7), very (7), another (7), practical (7), much (7), amount (7), between (7), believed (7), factorization (7), bounds (7), taken (7), page (6), was (6), control (6), related (6), numerical (6), differential (6), real (6), history (6), open (6), intractability (6), s2cid (6), versus (6), called (6), when (6), include (6), running (6), based (6), say (6), efficient (6), over (6), they (6), article (6), said (6), difficult (6), how (6), required (6), resource (6), following (6), binary (6), string (6), solving (6), what (6), output (6), languages (5), search (5), use (5), commons (5), retrieved (5), automata (5), programming (5), circuit (5), boolean (5), exptime (5), press (5), new (5), richard (5), combinatorial (5), commonly (5), solvable (5), bounded (5), definition (5), out (5), consider (5), even (5), often (5), does (5), only (5), takes (5), been (5), thesis (5), requires (5), contained (5), graphs (5), because (5), being (5), integers (5), upper (5), their (5), subsection (5), contents (4), view (4), statistics (4), terms (4), category (4), short (4), study (4), states (4), research (4), biology (4), engineering (4), algebraic (4), arithmetic (4), geometry (4), equations (4), abstract (4), type (4), order (4), future (4), electronic (4), design (4), computability (4), requirements (4), specific (4), tools (4), acm (4), proof (4), dspace (4), exponential (4), infeasible (4), bqp (4), feasible (4), links (4), bibcode (4), fortnow (4), 2003 (4), cook (4), york (4), 2009 (4), karp (4), archived (4), original (4), among (4), functions (4), institute (4), babai (4), proved (4), paper (4), edmonds (4), similarly (4), indeed (4), sense (4), intractable (4), cobham (4), etc (4), deciding (4), prime (4), where (4), sqrt (4), means (4), equally (4), reduced (4), notion (4), multiplication (4), into (4), bound (4), mathsf (4), probabilistic (4), tape (4), within (4), usually (4), notation (4), random (4), hide (4), move (4), sidebar (4), statement (3), under (3), organization (3), wikimedia (3), wikidata (3), september (3), lists (3), optimization (3), game (3), probability (3), finite (3), complex (3), linear (3), logic (3), management (3), technology (3), processing (3), digital (3), social (3), modeling (3), multi (3), hardware (3), world (3), wide (3), process (3), development (3), form (3), consumption (3), expspace (3), considered (3), suspected (3), why (3), tractable (3), 1109 (3), arxiv (3), 0001 (3), 1145 (3), stephen (3), studies (3), michael (3), 2008 (3), cambridge (3), computers (3), 2000 (3), springer (3), barak (3), computations (3), reducibility (3), trakhtenbrot (3), 1962 (3), july (3), lászló (3), journal (3), millennium (3), clay (3), ladner (3), chapter (3), references (3), blum (3), axioms (3), earlier (3), definitions (3), before (3), done (3), refer (3), small (3), practice (3), program (3), makes (3), run (3), independent (3), times (3), cases (3), shown (3), less (3), solutions (3), those (3), cannot (3), logarithmic (3), strictly (3), collapse (3), subseteq (3), basis (3), will (3), level (3), respect (3), intermediate (3), vertices (3), although (3), examples (3), question (3), types (3), prize (3), like (3), efficiently (3), member (3), both (3), likely (3), every (3), squaring (3), multiplying (3), way (3), interesting (3), make (3), needed (3), circuits (3), account (3), determinism (3), concrete (3), stated (3), together (3), otherwise (3), analyzing (3), show (3), just (3), sorting (3), costly (3), amortized (3), distribution (3), measuring (3), expressed (3), viewed (3), communication (3), precise (3), total (3), solves (3), difficulty (3), analyze (3), actions (3), bits (3), powerful (3), connected (3), salesman (3), encoded (3), whose (3), encoding (3), alphabet (3), through (3), table (2), mobile (2), contact (2), privacy (2), policy (2), available (2), additional (2), categories (2), link (2), long (2), value (2), description (2), articles (2), fields (2), org (2), portal (2), art (2), mathematicians (2), informal (2), topics (2), algebra (2), physics (2), chemistry (2), applied (2), analytic (2), euclidean (2), combinatorics (2), calculus (2), elementary (2), philosophy (2), foundations (2), major (2), enterprise (2), graphics (2), task (2), distributed (2), method (2), representation (2), intelligence (2), parallel (2), visualization (2), interaction (2), human (2), virtual (2), application (2), methods (2), library (2), storage (2), randomized (2), algorithmic (2), integrated (2), framework (2), operating (2), performance (2), architecture (2), scale (2), interactive (2), nspace (2), ntime (2), nexptime (2), qma (2), zpp (2), should (2), 1994 (2), encyclopedia (2), free (2), external (2), 2002 (2), issn (2), lance (2), homer (2), current (2), 201 (2), proceedings (2), surveys (2), course (2), introduction (2), sipser (2), 1st (2), addison (2), wesley (2), university (2), conceptual (2), goldreich (2), series (2), sciences (2), john (2), parameterized (2), boaz (2), modern (2), approach (2), arora (2), textbooks (2), 1972 (2), eds (2), june (2), boris (2), signalizing (2), transactions (2), 1956 (2), yamada (2), computable (2), ieee (2), lecture (2), hybrid (2), manuel (2), francisco (2), sieve (2), 1016 (2), october (2), 1998 (2), protein (2), structure (2), doesn (2), 2018 (2), citations (2), life (2), work (2), works (2), unsolved (2), limits (2), desirable (2), properties (2), existence (2), levin (2), term (2), myhill (2), sets (2), well (2), somewhat (2), studied (2), 1965 (2), laid (2), devoted (2), various (2), uses (2), always (2), still (2), impractical (2), realistic (2), sizes (2), generally (2), second (2), faster (2), grows (2), conversely (2), take (2), them (2), yet (2), reasonable (2), quadratic (2), satisfiability (2), ptime (2), theoretically (2), infinite (2), literally (2), though (2), nexp (2), unequal (2), either (2), proving (2), separations (2), determining (2), factor (2), fact (2), forms (2), recent (2), questions (2), ability (2), proofs (2), proposed (2), 000 (2), contains (2), special (2), hardest (2), could (2), might (2), finding (2), concept (2), allows (2), larger (2), captures (2), tells (2), subsetneq (2), precisely (2), defines (2), proper (2), quantitative (2), counting (2), npspace (2), nexpspace (2), bounding (2), relation (2), step (2), depend (2), single (2), complexities (2), corresponding (2), constant (2), common (2), factors (2), defining (2), classify (2), maximum (2), today (2), addresses (2), largest (2), assume (2), quicksort (2), uniform (2), others (2), define (2), state (2), steps (2), outputs (2), operate (2), length (2), exists (2), classifying (2), little (2), physically (2), want (2), extra (2), determine (2), branches (2), principle (2), rather (2), computed (2), traveling (2), decide (2), strings (2), objects (2), members (2), choice (2), tries (2), bitstrings (2), adjacency (2), representing (2), version (2), cities (2), latter (2), asks (2), appearance (2), upload (2), file (2), changes (2), read (2), english (2), create (2), donate (2), menu (2), add, topic, cookie, developers, code, conduct, legal, safety, contacts, disclaimers, apply, site, you, agree, registered, trademark, profit, foundation, inc, creative, attribution, sharealike, license, rendered, parsoid, last, edited, august, 2026, utc, hidden, cs1, volume, mdy, dates, 2017, https, index, php, title, computational_complexity_theory, oldid, 1371073639, yale, lux, israel, czech, republic, united, national, gnd, international, authority, databases, wikiproject, education, metamathematics, pseudomathematics, recreational, films, sociology, psychology, linguistics, geology, finance, economics, ethnomathematics, homotopy, geometric, topology, diophantine, trigonometry, synthetic, projective, convex, affine, harmonic, functional, multilinear, homological, group, commutative, glossary, timeline, areas, glossaries, outline, document, educational, word, video, games, voting, cyberwarfare, publishing, healthcare, differentiable, commerce, solid, image, compression, unit, photograph, manipulation, rendering, animation, cross, validation, reinforcement, unsupervised, supervised, learning, methodology, automated, planning, scheduling, vision, knowledge, reasoning, natural, artificial, multiprocessing, multithreading, concurrent, concurrency, ubiquitous, augmented, extended, reality, accessibility, centered, intrusion, detection, services, hacker, cryptography, retrieval, web, marketing, platform, data, mining, multimedia, support, geographic, database, efficiency, semantics, stochastic, source, team, maintenance, deployment, construction, flow, repository, configuration, environment, domain, compiler, paradigm, notations, quality, middleware, interpreter, service, evaluation, scheduler, components, protocol, networks, wireless, sensor, fault, tolerance, cyber, physical, embedded, dependability, processor, acceleration, automation, green, energy, soc, chip, integration, peripheral, printed, board, template, follows, roughly, 2012, classification, probabilistically, checkable, families, arithmetical, grzegorczyk, hierarchies, polyl, nonelementary, fnp, tfnp, apx, reg, acc, dlogtime, scott, aaronson, philosophers, care, ems, 2001, zoo, media, look, wiktionary, dictionary, mertens, stephan, physicists, 633346, 1521, 9615, 5992, 998639, 2002cse, 31m, cond, mat, 0012185, steven, 133, bulletin, eatcs, 1983, overview, 408, 14323396, 0782, 358141, 358144, 400, communications, khalil, hatem, 1976, review, partial, 15497394, 4503, 7489, 800191, 805573, 197, annual, conference, ulery, dana, 2nd, usa, thomson, 534, 95097, 53082, papadimitriou, christos, 1990, mit, 444, 88071, handbook, vol, van, leeuwen, jan, perspective, oded, 1979, books, 247570676, oclc, 0519066, 7167, 1045, freeman, company, guide, completeness, johnson, david, garey, ding, zhu, ker, wiley, sons, 471, 34506, downey, rod, 1999, monographs, berlin, verlag, 387, 94883, fellows, 1193, 68112, zbl, 521, 42426, sanjeev, miller, thatcher, plenum, 103, 2011, lncs, 4800, pillars, update, tabular, operators, uchionnye, zapiski, penzenskogo, pedinstituta, penza, pedagogoical, russian, recursive, 760, tec, 5219459, 1962irtec, 753y, 753, 1985, award, randomness, tomlin, claire, mitchell, ian, bayen, alexandre, techniques, verification, 1001, jproc, 814621, 2003ieeep, 986t, 986, oishi, meeko, campagnolo, survey, 0907, 3117, smale, steve, 1997, univ, 551, 5949193, 1017, s0962492900002774, 1997acnum, 523s, 523, acta, numerica, zobel, justin, 2015, 44716639, 132, writing, meurant, gerard, 2014, elsevier, 08093391, hopcroft, motwani, ullman, 2007, boston, san, 368, wolfram, mathworld, weblog, com, blog, factoring, 2016, quasipolynomial, 1512, 03547, 1988, low, 323, 0022, 0000, 90010, 312, schöning, uwe, arvind, vikraman, kurur, piyush, spp, 852, 002, 835, 204, notices, ams, grand, challenge, jaffe, arthur, april, december, 2010, folding, hydrophobic, hydrophilic, 9541869, pmid, 1089, cmb, leighton, berger, bonnie, 1975, 171, 14352974, 321864, 321877, 151, matter, www, claymath, wuppuluri, shyam, doria, 2020, scientific, 198790362, 981, 0006, 1142, 11270, unravelling, gregory, chaitin, transcomputational, structural, leaf, descriptive, 1967, formulated, now, specifying, result, began, flourish, 1971, practically, relevant, took, idea, leap, forward, his, landmark, showed, diverse, infamous, leonid, speed, initial, interest, increasingly, aside, favor, exciting, fusion, inherited, arsenal, ideas, had, occurred, 1955, coined, nowadays, switching, papers, studying, 1960, rudimentary, 1961, pioneer, ussr, remembers, hisao, raymond, smullyan, beginning, systematic, attributed, seminal, addition, suggested, good, stearns, juris, hartmanis, actual, explicitly, started, off, numerous, were, researchers, influential, 1936, turned, robust, flexible, simplification, alan, early, 1844, gabriel, lamé, modelling, dynamical, analog, involve, approximated, discretizations, unreasonable, useless, except, unusable, halting, 100, assuming, sake, years, magnitude, useful, technological, progress, until, gets, relatively, age, universe, identification, inexact, degree, leading, coefficient, quickly, slowly, saying, imply, written, range, routinely, handle, sat, solvers, knapsack, presburger, frequently, identified, impractically, near, handled, sometimes, interchangeably, risks, confusion, explosion, currently, again, distinct, along, lines, containing, answers, reversed, proven, clear, whence, complement, breakthrough, phrased, several, cryptographic, first, odd, unfortunately, lies, shor, left, frac, right, rsa, least, collapses, widely, due, offers, potentially, perspectives, eugene, luks, isomorphic, exist, neither, nor, few, logarithm, neq, equals, implications, find, resolving, pure, prediction, logistics, seen, abstraction, tasks, admit, hypothesis, hand, people, easily, observed, vertex, cover, hamiltonian, path, diagram, provided, outside, established, ones, able, reduce, indicate, yield, mean, motivates, harder, depends, square, giving, transformation, reduces, separation, results, cdot, prove, relaxing, bigger, know, inclusion, strict, respectively, induce, constraining, respective, pairs, properly, included, having, deduced, inclusions, proceed, statements, increase, turns, savitch, represent, constraint, manner, inside, above, yields, chosen, necessarily, allow, variations, polynomially, mid, complicated, fit, typical, depth, monotone, promise, simpler, hides, smaller, details, write, 15n, similar, helpful, demonstrate, unless, specified, falls, needs, phrase, includes, discovered, showing, pivot, smallest, never, divided, permutations, occurs, pivoting, divides, half, needing, cheap, considers, whole, assumed, appear, three, ways, mathcal, analogous, made, tree, transitions, halts, interested, criteria, denoted, easier, unusual, allowed, branch, check, possibilities, once, compute, branching, exactly, standard, literature, perhaps, surprisingly, converted, without, providing, power, memory, alternate, vary, deterministically, access, basic, fixed, rules, supply, decisions, helps, added, feature, multiple, paths, clearly, meant, realizable, gives, rise, particularly, alternating, symmetric, device, manipulates, symbols, strip, intended, anything, advanced, supercomputer, mathematician, pencil, furthermore, everything, easy, mathematically, lambda, cellular, conway, ram, church, illustration, argues, admits, wish, require, calculated, typically, measured, increases, compared, tempting, think, richer, really, recast, triples, holds, triple, corresponds, numbers, expected, notable, arbitrary, consists, associated, obtain, central, alternatively, objective, aid, consideration, returns, accept, reject, alternately, theoretic, regularly, keep, discussion, enough, achieved, ensuring, representations, transformed, considering, must, suitably, represented, directly, via, matrices, further, highlight, difference, route, kilometres, passing, germany, asking, round, trip, sites, reason, milan, travelling, collection, possibly, empty, referred, confused, itself, refers, contrast, utterance, serve, primality, testing, tour, german, closely, key, distinction, former, whereas, appropriately, restricted, turn, imposing, restrictions, distinguishes, kinds, algorithmically, roles, seven, part, processors, gates, regarded, inherently, significant, whatever, formalizes, intuition, introducing, quantifying, focuses, according, usage, explores, relationships, classifications, mechanical, inherent, item, wikiversity, projects, printable, download, print, export, switch, legacy, parser, get, shortened, url, cite, permanent, here, talk, tiếng, việt, українська, türkçe, tagalog, ไทย, српски, srpski, slovenčina, simple, srpskohrvatski, српскохрватски, русский, română, português, norsk, bokmål, nederlands, bahasa, melayu, монгол, 한국어, 日本語, italiano, hrvatski, עברית, français, suomi, فارسی, euskara, español, ελληνικά, deutsch, čeština, català, বাংলা, български, azərbaycanca, asturianu, العربية, top, personal, pages, community, learn, help, contribute, events, navigation, jump, content,
Text of the page (random words):
xt poly n expspace o 2 poly n displaystyle o 2 text poly n time non deterministic ntime f n displaystyle f n o f n displaystyle o f n np o poly n displaystyle o text poly n nexptime o 2 poly n displaystyle o 2 text poly n deterministic dtime f n displaystyle f n o f n displaystyle o f n p o poly n displaystyle o text poly n exptime o 2 poly n displaystyle o 2 text poly n logarithmic space classes do not account for the space required to represent the problem it turns out that pspace npspace and expspace nexpspace by savitch s theorem other important complexity classes include bpp zpp and rp which are defined using probabilistic turing machines ac and nc which are defined using boolean circuits and bqp and qma which are defined using quantum turing machines p is an important complexity class of counting problems not decision problems classes like ip and am are defined using interactive proof systems all is the class of all decision problems hierarchy theorems edit main articles time hierarchy theorem and space hierarchy theorem for the complexity classes defined in this way it is desirable to prove that relaxing the requirements on say computation time indeed defines a bigger set of problems in particular although dtime n displaystyle n is contained in dtime n 2 displaystyle n 2 it would be interesting to know if the inclusion is strict for time and space requirements the answer to such questions is given by the time and space hierarchy theorems respectively they are called hierarchy theorems because they induce a proper hierarchy on the classes defined by constraining the respective resources thus there are pairs of complexity classes such that one is properly included in the other having deduced such proper set inclusions we can proceed to make quantitative statements about how much more additional time or space is needed in order to increase the number of problems that can be solved more precisely the time hierarchy theorem states that d t i m e o f n d t i m e f n log f n displaystyle mathsf dtime big o f n big subsetneq mathsf dtime big f n cdot log f n big the space hierarchy theorem states that d s p a c e o f n d s p a c e f n displaystyle mathsf dspace big o f n big subsetneq mathsf dspace big f n big the time and space hierarchy theorems form the basis for most separation results of complexity classes for instance the time hierarchy theorem tells us that p is strictly contained in exptime and the space hierarchy theorem tells us that l is strictly contained in pspace reduction edit main article reduction complexity many complexity classes are defined using the concept of a reduction a reduction is a transformation of one problem into another problem it captures the informal notion of a problem being at most as difficult as another problem for instance if a problem x displaystyle x can be solved using an algorithm for y displaystyle y x displaystyle x is no more difficult than y displaystyle y and we say that x displaystyle x reduces to y displaystyle y there are many different types of reductions based on the method of reduction such as cook reductions karp reductions and levin reductions and the bound on the complexity of reductions such as polynomial time reductions or log space reductions the most commonly used reduction is a polynomial time reduction this means that the reduction process takes polynomial time for example the problem of squaring an integer can be reduced to the problem of multiplying two integers this means an algorithm for multiplying two integers can be used to square an integer indeed this can be done by giving the same input to both inputs of the multiplication algorithm thus we see that squaring is not more difficult than multiplication since squaring can be reduced to multiplication this motivates the concept of a problem being hard for a complexity class a problem x displaystyle x is hard for a class of problems c displaystyle c if every problem in c displaystyle c can be reduced to x displaystyle x thus no problem in c displaystyle c is harder than x displaystyle x since an algorithm for x displaystyle x allows us to solve any problem in c displaystyle c the notion of hard problems depends on the type of reduction being used for complexity classes larger than p polynomial time reductions are commonly used in particular the set of problems that are hard for np is the set of np hard problems if a problem x displaystyle x is in c displaystyle c and hard for c displaystyle c then x displaystyle x is said to be complete for c displaystyle c this means that x displaystyle x is the hardest problem in c displaystyle c since many problems could be equally hard one might say that x displaystyle x is one of the hardest problems in c displaystyle c thus the class of np complete problems contains the most difficult problems in np in the sense that they are the ones most likely not to be in p because the problem p np is not solved being able to reduce a known np complete problem π 2 displaystyle pi _ 2 to another problem π 1 displaystyle pi _ 1 would indicate that there is no known polynomial time solution for π 1 displaystyle pi _ 1 this is because a polynomial time solution to π 1 displaystyle pi _ 1 would yield a polynomial time solution to π 2 displaystyle pi _ 2 similarly because all np problems can be reduced to the set finding an np complete problem that can be solved in polynomial time would mean that p np 3 important open problems edit diagram of complexity classes provided that p np the existence of problems in np outside both p and np complete in this case was established by ladner 4 p versus np problem edit main article p versus np problem the complexity class p is often seen as a mathematical abstraction modeling those computational tasks that admit an efficient algorithm this hypothesis is called the cobham edmonds thesis the complexity class np on the other hand contains many problems that people would like to solve efficiently but for which no efficient algorithm is known such as the boolean satisfiability problem the hamiltonian path problem and the vertex cover problem since deterministic turing machines are special non deterministic turing machines it is easily observed that each problem in p is also a member of the class np the question of whether p equals np is one of the most important open questions in theoretical computer science because of the wide implications of a solution 3 if the answer is yes many important problems can be shown to have more efficient solutions these include various types of integer programming problems in operations research many problems in logistics protein structure prediction in biology 5 and the ability to find formal proofs of pure mathematics theorems 6 the p versus np problem is one of the millennium prize problems proposed by the clay mathematics institute there is a us 1 000 000 prize for resolving the problem 7 problems in np not known to be in p or np complete edit it was shown by ladner that if p np displaystyle textsf p neq textsf np then there exist problems in np displaystyle textsf np that are neither in p displaystyle textsf p nor np displaystyle textsf np complete 4 such problems are called np intermediate problems the graph isomorphism problem the discrete logarithm problem and the integer factorization problem are examples of problems believed to be np intermediate they are some of the very few np problems not known to be in p displaystyle textsf p or to be np displaystyle textsf np complete the graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic an important unsolved problem in complexity theory is whether the graph isomorphism problem is in p displaystyle textsf p np displaystyle textsf np complete or np intermediate the answer is not known but it is believed that the problem is at least not np complete 8 if graph isomorphism is np complete the polynomial time hierarchy collapses to its second level 9 since it is widely believed that the polynomial hierarchy does not collapse to any finite level it is believed that graph isomorphism is not np complete the best algorithm for this problem due to lászló babai and eugene luks has run time o 2 n log n displaystyle o 2 sqrt n log n for graphs with n displaystyle n vertices although some recent work by babai offers some potentially new perspectives on this 10 the integer factorization problem is the computational problem of determining the prime factorization of a given integer phrased as a decision problem it is the problem of deciding whether the input has a prime factor less than k displaystyle k no efficient integer factorization algorithm is known and this fact forms the basis of several modern cryptographic systems such as the rsa algorithm the integer factorization problem is in np displaystyle textsf np and in co np displaystyle textsf co np and even in up and co up 11 if the problem is np displaystyle textsf np complete the polynomial time hierarchy will collapse to its first level i e np displaystyle textsf np will equal co np displaystyle textsf co np the best known algorithm for integer factorization is the general number field sieve which takes time o e 64 9 3 log n 3 log log n 2 3 displaystyle o e left sqrt 3 frac 64 9 right sqrt 3 log n sqrt 3 log log n 2 12 to factor an odd integer n displaystyle n however the best known quantum algorithm for this problem shor s algorithm does run in polynomial time unfortunately this fact doesn t say much about where the problem lies with respect to non quantum complexity classes separations between other complexity classes edit many known complexity classes are suspected to be unequal but this has not been proved for instance p np pp pspace displaystyle textsf p subseteq textsf np subseteq textsf pp subseteq textsf pspace but it is possible that p pspace displaystyle textsf p textsf pspace if p displaystyle textsf p is not equal to np displaystyle textsf np then p displaystyle textsf p is not equal to pspace displaystyle textsf pspace either since there are many known complexity classes between p displaystyle textsf p and pspace displaystyle textsf pspace such as rp displaystyle textsf rp bpp displaystyle textsf bpp pp displaystyle textsf pp bqp displaystyle textsf bqp ma displaystyle textsf ma ph displaystyle textsf ph etc it is possible that all these complexity classes collapse to one class proving that any of these classes are unequal would be a major breakthrough in complexity theory along the same lines co np displaystyle textsf co np is the class containing the complement problems i e problems with the yes no answers reversed of np displaystyle textsf np problems it is believed 13 that np displaystyle textsf np is not equal to co np displaystyle textsf co np however it has not yet been proven it is clear that if these two complexity classes are not equal then p displaystyle textsf p is not equal to np displaystyle textsf np since p co p displaystyle textsf p textsf co p thus if p n p displaystyle p np we would have co p co np displaystyle textsf co p textsf co np whence np p co p co np displaystyle textsf np textsf p textsf co p textsf co np similarly it is not known if l displaystyle textsf l the set of all problems that can be solved in logarithmic space is strictly contained in p displaystyle textsf p or equal to p displaystyle textsf p again there are many complexity classes between the two such as nl displaystyle textsf nl and nc displaystyle textsf nc and it is not known if they are distinct or equal classes it is suspected that p displaystyle textsf p and bpp displaystyle textsf bpp are equal however it is currently open if bpp nexp displaystyle textsf bpp textsf nexp intractability edit see also combinatorial explosion a problem that can theoretically be solved but requires impractically large near infinite amount of resources e g time to do so is known as an intractable problem 14 conversely a problem that can be solved in practice is called a tractable problem literally a problem that can be handled the term infeasible literally cannot be done is sometimes used interchangeably with intractable 15 though this risks confusion with a feasible solution in mathematical optimization 16 tractable problems are frequently identified with problems that have polynomial time solutions p displaystyle textsf p ptime displaystyle textsf ptime this is known as the cobham edmonds thesis problems that are known to be intractable in this sense include those that are exptime hard if np displaystyle textsf np is not the same as p displaystyle textsf p then np hard problems are also intractable in this sense however this identification is inexact a polynomial time solution with large degree or large leading coefficient grows quickly and may be impractical for practical size problems conversely an exponential time solution that grows slowly may be practical on realistic input or a solution that takes a long time in the worst case may take a short time in most cases or the average case and thus still be practical saying that a problem is not in p displaystyle textsf p does not imply that all large cases of the problem are hard or even that most of them are for example the decision problem in presburger arithmetic has been shown not to be in p displaystyle textsf p yet algorithms have been written that solve the problem in reasonable times in most cases similarly algorithms can solve the np complete knapsack problem over a wide range of sizes in less than quadratic time and sat solvers routinely handle large instances of the np complete boolean satisfiability problem to see why exponential time algorithms are generally unusable in practice consider a program that makes 2 n displaystyle 2 n operations before halting for small n displaystyle n say 100 and assuming for the sake of example that the computer does 10 12 displaystyle 10 12 operations each second the program would run for about 4 10 10 displaystyle 4 times 10 10 years which is the same order of magnitude as the age of the universe even with a much faster computer the program would only be useful for very small instances and in that sense the intractability of a problem is somewhat independent of technological progress however an exponential time algorithm that takes 1 0001 n displaystyle 1 0001 n operations is practical until n displaystyle n gets relatively large similarly a polynomial time algorithm is not always practical if its running time is say n 15 displaystyle n 15 it is unreasonable to consider it efficient and it is still useless except on small instances indeed in practice even n 3 displaystyle n 3 or n 2 displaystyle n 2 algorithms are often impractical on realistic sizes of problems continuous complexity theory edit continuous complexity theory can refer to complexity theory of problems that involve continuous functions that are approximated by discretizations as studied in numerical analysis one appro...
|
