The following pages link to (Q4298260):
Displayed 50 items.
- Backdoor sets of quantified Boolean formulas (Q1040783) (← links)
- The three-color and two-color Tantrix\(^{\text{TM}}\) rotation puzzle problems are NP-complete via parsimonious reductions (Q1041029) (← links)
- Flows with unit path capacities and related packing and covering problems (Q1041430) (← links)
- Properties of uniformly hard languages (Q1041777) (← links)
- Representing interval orders by weighted bases: some complexity results (Q1042324) (← links)
- The complexity of hybrid logics over equivalence relations (Q1047797) (← links)
- On the random generation and counting of matchings in dense graphs (Q1129018) (← links)
- Cellular automaton growth on \(\mathbb{Z}^2\): Theorems, examples, and problems (Q1271861) (← links)
- Approximating MAPs for belief networks is NP-hard and other theorems (Q1274288) (← links)
- Language complexity of rotations and Sturmian sequences (Q1274922) (← links)
- On the structure of Hamiltonian cycles in Cayley graphs of finite quotients of the modular group (Q1275470) (← links)
- Some complexity bounds for subtype inequalities (Q1275620) (← links)
- On the concavity of delivery games (Q1278793) (← links)
- \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\) (Q1288206) (← links)
- Succinctness as a source of complexity in logical formalisms (Q1302307) (← links)
- Sensitivity analysis for knapsack problems: Another negative result (Q1304487) (← links)
- The complexity of cover inequality separation (Q1306471) (← links)
- First-order linear logic without modalities is NEXPTIME-hard (Q1342252) (← links)
- Complexity of Langton's ant (Q1348376) (← links)
- Complexity of Presburger arithmetic with fixed quantifier dimension (Q1361890) (← links)
- The expressive powers of stable models for bound and unbound DATALOG queries (Q1362337) (← links)
- Computing optimal assignments for residual network reliability (Q1363776) (← links)
- The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate (Q1367098) (← links)
- Metafinite model theory (Q1383163) (← links)
- Some consequences of cryptographical conjectures for \(S_2^1\) and EF (Q1383164) (← links)
- Universally serializable computation (Q1384538) (← links)
- Is intractability of nonmonotonic reasoning a real drawback? (Q1391905) (← links)
- Farrell polynomials on graphs of bounded tree width (Q1398293) (← links)
- Generic-case complexity, decision problems in group theory, and random walks. (Q1399190) (← links)
- A polynomial space construction of tree-like models for logics with local chains of modal connectives (Q1399966) (← links)
- Tissue P systems. (Q1401274) (← links)
- P-immune sets with holes lack self-reducibility properties. (Q1401340) (← links)
- The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. (Q1401394) (← links)
- The complexity of bisimilarity-checking for one-counter processes. (Q1401395) (← links)
- On universally easy classes for NP-complete problems. (Q1401418) (← links)
- Orienting rewrite rules with the Knuth-Bendix order. (Q1401932) (← links)
- XML with data values: Typechecking revisited. (Q1401966) (← links)
- Connection caching: Model and algorithms. (Q1401982) (← links)
- \(\mathcal P = \mathcal{NP}\)? (Q1404168) (← links)
- On the polynomial-space completeness of intuitionistic propositional logic (Q1411664) (← links)
- (2+\(f\)(\(n\)))-SAT and its properties. (Q1421480) (← links)
- The decision problem of provability logic with only one atom (Q1423633) (← links)
- On the hardness of counting problems of complete mappings. (Q1426113) (← links)
- Reductions and functors from problems to word problems (Q1566706) (← links)
- The zero-one law holds for BPP (Q1575726) (← links)
- Intractability of decision problems for finite-memory automata (Q1575908) (← links)
- Computational complexity of planning and approximate planning in the presence of incompleteness (Q1583520) (← links)
- Clique is hard to approximate within \(n^{1-\epsilon}\) (Q1588908) (← links)
- The complexity of approximating MAPs for belief networks with bounded probabilities (Q1589640) (← links)
- Satisfying subtype inequalities in polynomial space (Q1605226) (← links)