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):
that the machines operate deterministically however some computational problems are easier to analyze in terms of more unusual resources for example a non deterministic turing machine is a computational model that is allowed to branch out to check many different possibilities at once the non deterministic turing machine has very little to do with how we physically want to compute algorithms but its branching exactly captures many of the mathematical models we want to analyze so that non deterministic time is a very important resource in analyzing computational problems complexity measures edit for a precise definition of what it means to solve a problem using a given amount of time and space a computational model such as the deterministic turing machine is used the time required by a deterministic turing machine m displaystyle m on input x displaystyle x is the total number of state transitions or steps the machine makes before it halts and outputs the answer yes or no a turing machine m displaystyle m is said to operate within time f n displaystyle f n if the time required by m displaystyle m on each input of length n displaystyle n is at most f n displaystyle f n a decision problem a displaystyle a can be solved in time f n displaystyle f n if there exists a turing machine operating in time f n displaystyle f n that solves the problem since complexity theory is interested in classifying problems based on their difficulty one defines sets of problems based on some criteria for instance the set of problems solvable within time f n displaystyle f n on a deterministic turing machine is then denoted by dtime f n displaystyle f n analogous definitions can be made for space requirements although time and space are the most well known complexity resources any complexity measure can be viewed as a computational resource complexity measures are very generally defined by the blum complexity axioms other complexity measures used in complexity theory include communication complexity circuit complexity and decision tree complexity the complexity of an algorithm is often expressed using big o notation best worst and average case complexity edit visualization of the quicksort algorithm which has average case performance o n log n displaystyle mathcal o n log n the best worst and average case complexity refer to three different ways of measuring the time complexity or any other complexity measure of different inputs of the same size since some inputs of size n displaystyle n may be faster to solve than others we define the following complexities best case complexity this is the complexity of solving the problem for the best input of size n displaystyle n average case complexity this is the complexity of solving the problem on average for inputs of size n this complexity is only defined with respect to a probability distribution over the inputs for instance if all inputs of the same size are assumed to be equally likely to appear the average case complexity can be defined with respect to the uniform distribution over all inputs of size n displaystyle n amortized analysis amortized analysis considers both the costly and less costly operations together over the whole series of operations of the algorithm worst case complexity this is the complexity of solving the problem for the worst input of size n displaystyle n the order from cheap to costly is best average of discrete uniform distribution amortized worst for example the deterministic sorting algorithm quicksort addresses the problem of sorting a list of integers the worst case is when the pivot is always the largest or smallest value in the list so the list is never divided in this case the algorithm takes time o n 2 displaystyle n 2 if we assume that all possible permutations of the input list are equally likely the average time taken for sorting is o n log n displaystyle o n log n the best case occurs when each pivoting divides the list in half also needing o n log n displaystyle o n log n time upper and lower bounds on the complexity of problems edit to classify the computation time or similar resources such as space consumption it is helpful to demonstrate upper and lower bounds on the maximum amount of time required by the most efficient algorithm to solve a given problem the complexity of an algorithm is usually taken to be its worst case complexity unless specified otherwise analyzing a particular algorithm falls under the field of analysis of algorithms to show an upper bound t n displaystyle t n on the time complexity of a problem one needs to show only that there is a particular algorithm with running time at most t n displaystyle t n however proving lower bounds is much more difficult since lower bounds make a statement about all possible algorithms that solve a given problem the phrase all possible algorithms includes not just the algorithms known today but any algorithm that might be discovered in the future to show a lower bound of t n displaystyle t n for a problem requires showing that no algorithm can have time complexity lower than t n displaystyle t n upper and lower bounds are usually stated using the big o notation which hides constant factors and smaller terms this makes the bounds independent of the specific details of the computational model used for instance if t n 7 n 2 15 n 40 displaystyle t n 7n 2 15n 40 in big o notation one would write t n o n 2 displaystyle t n in o n 2 complexity classes edit main article complexity class defining complexity classes edit a complexity class is a set of problems of related complexity simpler complexity classes are defined by the following factors the type of computational problem the most commonly used problems are decision problems however complexity classes can be defined based on function problems counting problems optimization problems promise problems etc the model of computation the most common model of computation is the deterministic turing machine but many complexity classes are based on non deterministic turing machines boolean circuits quantum turing machines monotone circuits etc the resource or resources that is being bounded and the bound these two properties are usually stated together such as polynomial time logarithmic space constant depth etc some complexity classes have complicated definitions that do not fit into this framework thus a typical complexity class has a definition like the following the set of decision problems solvable by a deterministic turing machine within time f n displaystyle f n this complexity class is known as dtime f n displaystyle f n but bounding the computation time above by some concrete function f n displaystyle f n often yields complexity classes that depend on the chosen machine model for instance the language x x x is any binary string displaystyle xx mid x text is any binary string can be solved in linear time on a multi tape turing machine but necessarily requires quadratic time in the model of single tape turing machines if we allow polynomial variations in running time cobham edmonds thesis states that the time complexities in any two reasonable and general models of computation are polynomially related goldreich 2008 chapter 1 2 this forms the basis for the complexity class p which is the set of decision problems solvable by a deterministic turing machine within polynomial time the corresponding set of function problems is fp important complexity classes edit a representation of the relation among complexity classes l would be another step inside nl many important complexity classes can be defined by bounding the time or space used by the algorithm some important complexity classes of decision problems defined in this manner are the following resource determinism complexity class resource constraint space non deterministic nspace f n displaystyle f n o f n displaystyle o f n nl o log n displaystyle o log n npspace o poly n displaystyle o text poly n nexpspace o 2 poly n displaystyle o 2 text poly n deterministic dspace f n displaystyle f n o f n displaystyle o f n l o log n displaystyle o log n pspace o poly n displaystyle o text 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 institut...
|
