Hubbry Logo
EXPTIMEEXPTIMEMain
Open search
EXPTIME
Community hub
EXPTIME
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
EXPTIME
EXPTIME
EXPTIME
View on Wikipedia
from Wikipedia

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2p(n)) time, where p(n) is a polynomial function of n.

EXPTIME is one intuitive class in an exponential hierarchy of complexity classes with increasingly more complex oracles or quantifier alternations. For example, the class 2-EXPTIME is defined similarly to EXPTIME but with a doubly exponential time bound. This can be generalized to higher and higher time bounds.

EXPTIME can also be reformulated as the space class APSPACE, the set of all problems that can be solved by an alternating Turing machine in polynomial space.

EXPTIME relates to the other basic time and space complexity classes in the following way: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE. Furthermore, by the time hierarchy theorem and the space hierarchy theorem, it is known that P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE.

Formal definition

[edit]

In terms of DTIME,

Relationships to other classes

[edit]

It is known that

P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE

and also, by the time hierarchy theorem and the space hierarchy theorem, that

P ⊊ EXPTIME, NP ⊊ NEXPTIME and PSPACE ⊊ EXPSPACE

In the above expressions, the symbol ⊆ means "is a subset of", and the symbol ⊊ means "is a strict subset of".

so at least one of the first three inclusions and at least one of the last three inclusions must be proper, but it is not known which ones are. It is also known that if P = NP, then EXPTIME = NEXPTIME, the class of problems solvable in exponential time by a nondeterministic Turing machine.[1] More precisely, E ≠ NE if and only if there exist sparse languages in NP that are not in P.[2]

EXPTIME can be reformulated as the space class APSPACE, the set of all problems that can be solved by an alternating Turing machine in polynomial space. This is one way to see that PSPACE ⊆ EXPTIME, since an alternating Turing machine is at least as powerful as a deterministic Turing machine.[3]

EXPTIME-complete

[edit]

A decision problem is EXPTIME-complete if it is in EXPTIME and every problem in EXPTIME has a polynomial-time many-one reduction to it. In other words, there is a polynomial-time algorithm that transforms instances of one to instances of the other with the same answer. Problems that are EXPTIME-complete might be thought of as the hardest problems in EXPTIME. Notice that although it is unknown whether NP is equal to P, we do know that EXPTIME-complete problems are not in P; it has been proven that these problems cannot be solved in polynomial time, by the time hierarchy theorem.

In computability theory, one of the basic undecidable problems is the halting problem: deciding whether a deterministic Turing machine (DTM) halts. One of the most fundamental EXPTIME-complete problems is a simpler version of this, which asks if a DTM halts on a given input in at most k steps. It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is encoded using O(log k) bits which causes exponential number of simulations. It is EXPTIME-complete because, roughly speaking, we can use it to determine if a machine solving an EXPTIME problem accepts in an exponential number of steps; it will not use more.[4] The same problem with the number of steps written in unary is P-complete.

Other examples of EXPTIME-complete problems include the problem of evaluating a position in generalized chess,[5] checkers,[6] or Go (with Japanese ko rules).[7] These games have a chance of being EXPTIME-complete because games can last for a number of moves that is exponential in the size of the board. In the Go example, the Japanese ko rule is known to imply EXPTIME-completeness, but it is not known if the American or Chinese rules for the game are EXPTIME-complete (they could range from PSPACE to EXPSPACE).

By contrast, generalized games that can last for a number of moves that is polynomial in the size of the board are often PSPACE-complete. The same is true of exponentially long games in which non-repetition is automatic.

Succinct circuits

[edit]

Another set of important EXPTIME-complete problems relates to succinct circuits. The idea is that if we can exponentially compress the description of a problem that requires polynomial time, then that compressed problem would require exponential time.

As one example, some graphs can be succinctly described by a small Boolean circuit. The circuit has inputs, 1 output and gates, thus requiring bits to describe. The circuit represents a graph with vertices. For each pair of vertices, if the binary code for the two vertices are put into the circuit, then the output of the circuit states whether the two vertices are connected by an edge.

For many naturally occurring P-complete decision problems about graphs, where the graph is expressed in a natural representation such as an adjacency matrix, solving the same problem on a succinct circuit representation is EXPTIME-complete, because the input is exponentially smaller; but this requires nontrivial proof, since succinct circuits can only describe a subclass of graphs.[8]

Generically, a Boolean circuit with inputs and a single output is a succinct representation of a string of bits, which can be used to describe some other object, such as a graph, a 3-CNF formula, etc. For essentially all known NP-complete problems, the succinct version of it is NEXP-complete. In particular, SUCCINCT 3-SAT is NEXP-complete under polynomial-time reductions.[9][10]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

EXPTIME

View on Grokipedia
from Grokipedia
EXPTIME is a in consisting of all decision problems that can be solved by a deterministic in exponential time, formally defined as the union over all constants k≥0k \geq 0 of the time complexity classes TIME(2nk)\mathsf{TIME}(2^{n^k}), where nn is the length of the input. This means problems in EXPTIME can be decided in time bounded by O(2p(n))O(2^{p(n)}) for some p(n)p(n). EXPTIME relates to other fundamental complexity classes through a series of strict inclusions under standard assumptions. It contains PSPACE, the class of problems solvable in polynomial space, because any polynomial-space computation can be simulated in exponential time by exploring all possible configurations. Conversely, EXPTIME is contained within NEXPTIME, the nondeterministic exponential-time class, as deterministic computations are a special case of nondeterministic ones. Additionally, P ⊆\subseteq NP ⊆\subseteq PSPACE ⊆\subseteq EXPTIME ⊆\subseteq NEXPTIME ⊆\subseteq EXPSPACE, with the equalities PSPACE = NPSPACE and EXPSPACE = NEXPSPACE holding by , though separations like PSPACE ≠\neq EXPTIME are widely believed but unproven. Problems complete for EXPTIME under polynomial-time reductions capture the hardest problems in the class and include several from and logic. For example, determining the winner in n×nn \times n (generalized checkers on an n×nn \times n board) is EXPTIME-complete, requiring analysis of an exponential number of possible moves. Other notable EXPTIME-complete problems involve deciding outcomes in generalized games like chess or Go on variable-sized boards, as well as evaluating certain alternating quantified formulas or acceptance by succinct alternating Turing machines. These completeness results highlight EXPTIME's role in modeling computationally intensive tasks that exceed polynomial-time solvability but remain within exponential bounds.

Introduction

Overview and Motivation

EXPTIME is the complexity class comprising all decision problems solvable by a deterministic Turing machine in exponential time, specifically within a bound of 2nk2^{n^k} steps for some constant k≥1k \geq 1, where nn denotes the input size. This class captures computations that, while feasible in theory, grow dramatically with input length due to the exponential nature of the time requirement, placing it above polynomial-time classes in the computational hierarchy. For instance, EXPTIME sits at the first level of the exponential hierarchy and strictly contains PSPACE under standard assumptions, teasing the broader structure where P ⊆\subseteq NP ⊆\subseteq PSPACE ⊆\subseteq EXPTIME. The motivation for studying EXPTIME lies in its role as a boundary for decidable yet highly resource-intensive problems, distinguishing them from undecidable ones like the while underscoring the practical limits of exponential growth in algorithm design. Problems in EXPTIME highlight scenarios where brute-force of vast state spaces is possible but inefficient, informing when or heuristics become necessary in fields like verification and . A key example is determining the winner in generalized chess played on an n×nn \times n board with standard rules, which requires exponential time in the worst case, illustrating how game-theoretic decisions scale beyond feasibility. The formalization of EXPTIME emerged in the 1970s amid foundational advances in complexity theory. In , Hartmanis and Stearns established the framework for measuring via time and space bounds on Turing machines, laying groundwork for class definitions. By 1970, linked nondeterministic and deterministic space classes, influencing exponential bounds. Meyer and Stockmeyer then formalized the in 1972 and expanded on exponential classes, solidifying EXPTIME's place in the landscape of decidable problems during this pivotal decade.

Historical Development

The origins of EXPTIME trace back to the mid-1960s, when Juris Hartmanis and Richard E. Stearns developed foundational measures of based on time resources for Turing machines. In their seminal 1965 paper, they proved the time hierarchy theorem, demonstrating that Turing machines running in time bounded by a function f(n)f(n) can solve strictly more problems than those bounded by a slower-growing g(n)g(n) where g(n)=o(f(n)log⁡f(n))g(n) = o(f(n) \log f(n)), which established distinct complexity classes including those requiring exponential time, such as DTIME(2cn)\mathsf{DTIME}(2^{cn}) for constants c>0c > 0. This work laid the groundwork for separating polynomial-time classes from exponential ones, influencing the broader structure of deterministic time complexity. In the 1970s, the class EXPTIME was more formally delineated amid advancements in the polynomial hierarchy and analyses of space-time tradeoffs. Stephen Cook's 1971 paper on NP-completeness implicitly positioned EXPTIME as a containing class for NP, since nondeterministic polynomial time is subsumed by deterministic exponential time, while subsequent works by Cook and others, such as the 1973 nondeterministic time hierarchy theorem, further clarified separations within exponential bounds. These developments highlighted EXPTIME's role in encompassing problems beyond polynomial resources, with space-time tradeoff results, including conversions showing that polynomial space implies exponential time, solidifying its place in the hierarchy. A pivotal advancement came in 1970 with , which proved that nondeterministic space s(n)s(n) is contained in deterministic space s2(n)s^2(n), yielding PSPACE=NPSPACE\mathsf{PSPACE} = \mathsf{NPSPACE} and, by standard space-to-time simulations, PSPACE⊆EXPTIME\mathsf{PSPACE} \subseteq \mathsf{EXPTIME}. This result, combined with later nondeterministic time hierarchy theorems by Cook in 1973 and Seiferas, Furst, and Meyer in 1978, provided rigorous separations and inclusions involving EXPTIME, confirming its position above PSPACE while below higher exponential classes. EXPTIME played a central role in the formulation of the exponential hierarchy in the early 1980s, an analog to the polynomial hierarchy but relativized to exponential time oracles, with levels ΣkE\mathsf{\Sigma}_k^E and ΠkE\mathsf{\Pi}_k^E starting from EXPTIME=Σ1E\mathsf{EXPTIME} = \mathsf{\Sigma}_1^E and NEXPTIME=Σ1E,NP\mathsf{NEXPTIME} = \mathsf{\Sigma}_1^{E,\mathsf{NP}}. This structure, explored in works like those of Hartmanis, Sewelson, and Immerman in 1983 on sparse sets, extended the alternating quantifier framework to exponential resources. Additionally, the 1981 equivalence APSPACE=EXPTIME\mathsf{APSPACE} = \mathsf{EXPTIME} by Chandra, Kozen, and Stockmeyer underscored EXPTIME's connections to alternating space models.

Formal Foundations

Mathematical Definition

EXPTIME is the complexity class consisting of all decision problems solvable by a deterministic Turing machine in exponential time, formally defined as EXPTIME=⋃k≥1DTIME(2nk),\text{EXPTIME} = \bigcup_{k \geq 1} \text{DTIME}(2^{n^k}), where DTIME(f(n))\text{DTIME}(f(n)) is the class of languages decided by a deterministic Turing machine in O(f(n))O(f(n)) time. Here, nn denotes the length of the input, and 2nk2^{n^k} bounds the running time exponentially, with the exponent being polynomial in nn. More precisely, a LL belongs to EXPTIME if there exists a deterministic MM and an constant k≥1k \geq 1 such that, for every input string xx with ∣x∣=n|x| = n, the machine MM halts and correctly decides membership of xx in LL within at most 2nk2^{n^k} steps. This model typically employs multi-tape Turing machines, with the input provided on a dedicated read-only tape that the machine accesses using only O(log⁡n)O(\log n) space, while additional read-write work tapes store intermediate computations. The deterministic character of the underlying sets EXPTIME apart from , which allows nondeterministic choices in the . For context, polynomial-time solvable problems in are contained within EXPTIME.

Equivalent Formulations

EXPTIME is equivalently characterized as the class APSPACE, consisting of the languages accepted by s using . An extends the nondeterministic model by incorporating both existential and universal states: existential states branch to accepting successor configurations if at least one branch accepts, while universal states require all successor configurations to accept. This alternation allows the machine to simulate exponential-time computations within bounds, as the computation tree's depth is limited by the space usage, leading to at most exponentially many configurations. The equivalence APSPACE = EXPTIME was established by showing that any alternating Turing machine operating in polynomial space can be simulated by a deterministic exponential-time , and conversely, any deterministic exponential-time can be expressed as an alternating polynomial-space acceptance problem. Specifically, the simulation involves evaluating the alternating tree by recursively checking existential and universal branches, which unfolds into a deterministic exponential-time procedure due to the polynomial space implying an exponential number of possible configurations. For the reverse direction, an exponential-time deterministic machine's configuration graph, of exponential size, can be explored using alternating quantification over polynomial-space representations of paths. Another formulation arises from nondeterministic Turing machines, where EXPTIME corresponds to the deterministic exponential-time class, but with nondeterministic exponential time () containing it; however, under restrictions like closure properties, certain nondeterministic exponential-time problems coincide with EXPTIME via complementation. The Immerman-Szelepcsényi theorem, proving that nondeterministic space classes are closed under complement, supports these space-time equivalences by enabling simulations of co-nondeterministic computations in the same space, which indirectly bolsters the alternating space characterization of EXPTIME. The inclusion PSPACE ⊆ EXPTIME follows from , which establishes NPSPACE = PSPACE, implying that polynomial-space computations, whether deterministic or nondeterministic, can be simulated deterministically in exponential time by exploring the exponential-sized configuration graph. This simulation counts satisfying paths or configurations using a recursive doubling technique: to check from configuration A to B in 2^k steps, enumerate midpoints and verify subpaths, yielding a time bound of O((s(n))^4) where s(n) is space, thus exponential overall. For APSPACE, this combines with alternation to fully equate it to EXPTIME, as the polynomial-space alternating machine's acceptance reduces to a quantified boolean formula evaluation, embeddable in exponential time.

Complexity Hierarchy

Inclusions and Separations

EXPTIME occupies a central position in the polynomial and exponential hierarchies of complexity classes, with well-established inclusions relating it to neighboring classes. The standard chain of inclusions is P \subseteq NP \subseteq \subseteq EXPTIME \subseteq \subseteq . The inclusion P \subseteq NP follows directly from the definition, as deterministic polynomial-time computation is a special case of nondeterministic polynomial-time computation. NP \subseteq holds because any nondeterministic polynomial-time machine uses at most polynomial space, and by , nondeterministic space classes equal their deterministic counterparts up to a quadratic factor, placing NP within . \subseteq EXPTIME arises from the general fact that any language accepted in space s(n) can be decided in time 2^{O(s(n))}, so polynomial space implies exponential time via configuration enumeration. EXPTIME \subseteq is immediate, as deterministic exponential time is contained in nondeterministic exponential time. Finally, \subseteq follows from simulating nondeterministic exponential-time computation using exponential space to track configurations, as the space used by the machine itself is at most exponential. Strict separations confirm that these inclusions are proper in key cases. The deterministic time hierarchy theorem establishes P \subsetneq EXPTIME, as there exist time-constructible functions f(n) and g(n) with f(n) \log f(n) = o(g(n)) implying DTIME(f(n)) \subsetneq DTIME(g(n)); taking f(n) = n^k for constant k and g(n) = 2^n yields the separation. Similarly, the nondeterministic time hierarchy theorem shows NP \subsetneq EXPTIME, since NTIME(n^k) \subsetneq NTIME(2^n) under the same condition on time-constructible bounds. A key proof sketch for PSPACE \subseteq EXPTIME relies on , which states that for space-constructible s(n) \geq \log n, NSPACE(s(n)) \subseteq DSPACE(s(n)^2); thus NPSPACE \subseteq DSPACE(n^2) for polynomial n, and since PSPACE = NPSPACE, PSPACE \subseteq DSPACE(n^2). Any deterministic space-s(n) computation can then be simulated in time 2^{O(s(n))} by enumerating reachable configurations, so DSPACE(n^2) \subseteq DTIME(2^{O(n)}), placing PSPACE in EXPTIME. Even under assumptions like P = NP, which causes the to collapse to P, EXPTIME remains strictly larger than P by the time hierarchy theorem. Oracle separations further illustrate the hierarchy's structure, with relativization techniques showing that certain inclusions relativize while separations do not always; for instance, the Baker-Gill-Solovay theorem constructs oracles A and B where P^A = NP^A but P^B \neq NP^B, and extensions yield oracles separating exponential classes from polynomial-oracle enhancements, such as EXPTIME \neq EXPTIME^P in some relativized worlds.

Equivalences with Other Classes

EXPTIME is equivalent to APSPACE, the class of problems solvable by an in polynomial space. This equivalence was established by , Kozen, and Stockmeyer in their seminal work on alternating Turing machines, which demonstrated that alternating polynomial space computations precisely capture exponential time. The proof relies on two directions: first, any exponential-time computation can be simulated by an alternating machine using polynomial space through a configuration graph where existential states guess successors and universal states verify all possibilities; second, any alternating polynomial-space machine can be simulated deterministically in exponential time by recursively evaluating the game tree of existential and universal moves. Stockmeyer's contributions to the theory of alternating complexity classes further solidify this placement, showing that APSPACE sits exactly at the level of within the broader alternation hierarchy, where increasing alternations correspond to higher exponential levels. This result highlights the power of alternation in compressing resource bounds, allowing polynomial space with alternations to match the expressive power of exponential time without them. EXPTIME also admits a deterministic space characterization as the union over all constants kk of the classes DSPACE(2nk/n)\mathsf{DSPACE}(2^{n^k}/n). This identity arises from general time-space simulation theorems, which show that deterministic time t(n)t(n) can be simulated in space t(n)/log⁡t(n)t(n)/\log t(n); applying this to exponential time bounds yields the sub-exponential space form. Such equivalences underscore the deep connections between time and space measures in complexity theory, enabling translations between models. Within the exponential hierarchy—a structure analogous to the but defined via alternating exponential-time classes—EXPTIME occupies the base level, corresponding to the deterministic exponential-time computations that initiate the hierarchy's progression through increasing alternation depths. This positioning implies that separations or collapses at the EXPTIME level would propagate upward, affecting higher levels like 2-EXPTIME. The equivalence between EXPTIME and APSPACE has profound implications for the broader hierarchy: since PSPACE coincides with the non-alternating polynomial space and is contained in EXPTIME, an equality PSPACE = EXPTIME would force the to collapse to PSPACE, as the latter contains the entire via bounded-alternation simulations. Although no unconditional separations are known between PSPACE and EXPTIME, relativized worlds and natural proofs suggest the inclusion is strict, preserving the hierarchy's structure.

Completeness and Hardness

EXPTIME-Complete Problems

A is EXPTIME-complete if it lies in EXPTIME and every language in EXPTIME reduces to it via a ; are commonly employed to demonstrate completeness. These preserve the exponential computational blowup inherent to EXPTIME problems, as a maps an input of size nn to an instance of size at most ncn^c for some constant cc, allowing the target problem's exponential-time solver to handle the original computation efficiently. Prominent examples of EXPTIME-complete problems arise from generalized versions of classic board games, where the board size nn is part of the input, leading to an exponential number of possible moves. Determining whether the first player has a winning strategy in generalized chess on an n×nn \times n board from a given position is EXPTIME-complete. Similarly, deciding the winner in n×nn \times n under standard rules (with forced captures) is EXPTIME-complete. Generalized Go on an n×nn \times n board with Japanese ko rules also requires exponential time to solve for a winning strategy, establishing its EXPTIME-completeness. The first natural EXPTIME-complete problems via such games were established in the early , with Fraenkel and Lichtenstein proving completeness for generalized chess. Another foundational example is the succinct circuit value problem: given a CC succinctly described by a smaller circuit DD that outputs the bits of CC on query, and inputs to CC, does CC evaluate to 1? This is EXPTIME-complete because evaluating the expanded circuit takes exponential time in the size of DD. A canonical non-game example is the exponential-time bounded halting problem: given a deterministic MM, input ww, and unary time bound 1t1^t, does MM halt on ww within 2t2^t steps? Membership in EXPTIME follows from direct , which runs in time exponential in the input size Θ(t+∣M∣+∣w∣)\Theta(t + |M| + |w|), while hardness is shown by reducing arbitrary EXPTIME languages via time-bound padding. This can be formalized using quantified formulas with exponentially many alternating quantifiers, where evaluating truth requires exponential time analogous to the halting .

Succinct Representations

Succinct representations provide a powerful technique for establishing EXPTIME-completeness by encoding exponentially large instances of easier problems using polynomial-sized descriptions, thereby amplifying the to exponential time in the description size. A key example is the use of succinct circuits, which are small circuits that, given binary indices i and j as input, output the entry in the of a much larger implicit graph with 2^n vertices, where n is the size of the succinct circuit. This compression allows polynomial-time solvable graph problems to require exponential time when the graph is given succinctly, as querying the implicit demands exploring an exponential number of edges or vertices. The succinct graph connectivity problem exemplifies this approach: given a succinct circuit defining a graph and two vertices specified by indices, determine if there is a path between them. This problem is . For membership in , the succinct circuit enables adjacency queries in polynomial time, and connectivity can be decided using nondeterministic space-bounded algorithms like , simulating the exponential graph in polynomial space. Hardness for follows from a reduction that encodes computations (e.g., via QBF evaluation) into the succinct graph structure, where path existence corresponds to . Similarly, the Succinct Circuit Value Problem (SCVP) asks whether a , succinctly described by another circuit that, on query to an index, outputs the corresponding bits of the circuit's (such as type and connections), evaluates to 1 on a given input. SCVP is EXPTIME-complete, serving as a hardness tool. Evaluating the implicit exponential-sized circuit requires computing up to 2^{poly(n)} , placing it in EXPTIME via on-demand evaluation using the succinct descriptor. For EXPTIME-hardness, from complete problems like deterministic exponential-time acceptance map the computation tableau into a large circuit succinctly encoded by a polynomial-sized circuit describing the transition function and configuration updates. This succinctness paradigm extends the key reduction technique from EXPTIME-complete problems such as TQBF variants or finite games to their compressed forms, where the describing circuit has size logarithmic in the original instance size. For instance, encoding a large game's state graph succinctly turns polynomial-time game solving into an EXPTIME-complete task, as simulating the exponential number of states requires exponential effort. Overall, succinct representations demonstrate how compression can elevate the of a problem from to exponential time.

References

  1. https://cs.brown.edu/people/jsavage/book/pdfs/ModelsOfComputation_Chapter8.pdf
  2. https://complexityzoo.net/Complexity_Zoo:E
  3. http://kilby.stanford.edu/~rvg/154/handouts/complexity.html
  4. https://introcs.cs.princeton.edu/papers/checkers.pdf
  5. https://www.math.uri.edu/~billk/pubs/CRexptime.pdf
  6. https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/cd36299a637326d7b52d89d9261036e3_MIT18_404f20_lec22.pptx
  7. https://plato.stanford.edu/entries/computational-complexity/
  8. https://www.sciencedirect.com/science/article/pii/0097316581900169
  9. https://www.ams.org/journals/tran/1965-117-00/S0002-9947-1965-0170805-7/S0002-9947-1965-0170805-7.pdf
  10. https://lance.fortnow.com/papers/files/history.pdf
  11. https://theory.cs.princeton.edu/complexity/derandchap.pdf
  12. https://users.cs.duke.edu/~reif/courses/complectures/Arora/lec1.pdf
  13. https://www.cs.swarthmore.edu/~fontes/cs46/20s/misc/Sipser-ch7.pdf
  14. http://www.cs.ox.ac.uk/people/paul.goldberg/CC/2021-22/slides7.pdf
  15. https://users.cs.duke.edu/~reif/courses/complectures/Arora/lec3.pdf
  16. https://people.seas.harvard.edu/~salil/cs221/spring10/lec2.pdf
  17. https://users.cs.duke.edu/~reif/courses/complectures/books/AB/phchap.pdf
  18. https://epubs.siam.org/doi/10.1137/0204037
  19. https://dl.acm.org/doi/10.1145/322234.322243
  20. https://epubs.siam.org/doi/10.1137/0213018
  21. https://users.cs.duke.edu/~reif/courses/complectures/Umans/lec2c.pdf
  22. https://inria.hal.science/hal-01256660/file/gocomplexities_draft.pdf
  23. https://williamhoza.com/teaching/spring2024-intro-to-complexity/c19-poly-time-reductions.pdf
  24. https://www.sciencedirect.com/science/article/pii/S0019995883800047
  25. https://ocw.mit.edu/courses/18-405j-advanced-complexity-theory-spring-2016/491cab2df022fe59ff5f6adbe2cbb2a7_MIT18_405JS16_SuinctlyEcod.pdf
Add your contribution
Related Hubs
User Avatar
No comments yet.