Which problems have strongly exponential complexity?

DOI10.1006/JCSS.2001.1774zbMath1006.68052DBLPjournals/jcss/ImpagliazzoPZ01OpenAlexW1995725694WikidataQ55891730 ScholiaQ55891730MaRDI QIDQ1604206

Russell Impagliazzo, Ramamohan Paturi, Francis Zane

Publication date: 4 July 2002

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.2001.1774

zbMATH Keywords

NP-complete problemssub-exponential reduction family

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (only showing first 100 items - show all)

Improved Lower Bounds for Graph Embedding Problems ⋮ Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems ⋮ Cluster Editing ⋮ Computing list homomorphisms in geometric intersection graphs ⋮ Complexity of \(C_k\)-coloring in hereditary classes of graphs ⋮ Subcubic Equivalences between Graph Centrality Problems, APSP, and Diameter ⋮ Parameterized algorithms and data reduction for the short secluded s‐t‐path problem ⋮ A note on hardness of computing recursive teaching dimension ⋮ On the complexity of the storyplan problem ⋮ Linear‐time algorithms for eliminating claws in graphs ⋮ The 2CNF Boolean formula satisfiability problem and the linear space hypothesis ⋮ Improved (In-)Approximability Bounds for d-Scattered Set ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ How to find a good explanation for clustering? ⋮ Non-interactive universal arguments ⋮ FPT algorithms for packing \(k\)-safe spanning rooted sub(di)graphs ⋮ Solving infinite-domain CSPs using the patchwork property ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ What Is Known About Vertex Cover Kernelization? ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Balanced connected partitions of graphs: approximation, parameterization and lower bounds ⋮ Computing maximum matchings in temporal graphs ⋮ Unnamed Item ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ A polyhedral perspective on tropical convolutions ⋮ Filling crosswords is very hard ⋮ The pumping lemma for regular languages is hard ⋮ Communication and information complexity ⋮ Unnamed Item ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ Unnamed Item ⋮ Many Visits TSP Revisited ⋮ The Optimal Design of Low-Latency Virtual Backbones ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Slightly Superexponential Parameterized Problems ⋮ On the complexity of \(k\)-SAT ⋮ Component order connectivity in directed graphs ⋮ Intersection graphs of non-crossing paths ⋮ Complexity of the (Connected) Cluster Vertex Deletion Problem on H-free Graphs ⋮ Strong triadic closure in cographs and graphs of low maximum degree ⋮ On Structural Parameterizations of the Harmless Set Problem ⋮ Turán’s Theorem Through Algorithmic Lens ⋮ Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ Sparse graphs with bounded induced cycle packing number have logarithmic treewidth ⋮ Parameterized aspects of triangle enumeration ⋮ When can graph hyperbolicity be computed in linear time? ⋮ Ruling out FPT algorithms for weighted coloring on forests ⋮ Default logic and bounded treewidth ⋮ Optimality program in segment and string graphs ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Bounding the Running Time of Algorithms for Scheduling and Packing Problems ⋮ On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT ⋮ Parameterized Complexity of Directed Steiner Tree on Sparse Graphs ⋮ On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT ⋮ On the complexity of finding internally vertex-disjoint long directed paths ⋮ On cycle transversals and their connected variants in the absence of a small linear forest ⋮ Parameterized complexity of min-power asymmetric connectivity ⋮ Your rugby mates don't need to know your colleagues: triadic closure with edge colors ⋮ On the complexity of finding large odd induced subgraphs and odd colorings ⋮ Parameterized complexity of conflict-free set cover ⋮ The double exponential runtime is tight for 2-stage stochastic ILPs ⋮ Graph square roots of small distance from degree one graphs ⋮ Computing maximum independent set on outerstring graphs and their relatives ⋮ Obtaining a proportional allocation by deleting items ⋮ The perfect matching cut problem revisited ⋮ The double exponential runtime is tight for 2-stage stochastic ILPs ⋮ Recognizing \(k\)-clique extendible orderings ⋮ The perfect matching cut problem revisited ⋮ An EPTAS for scheduling on unrelated machines of few different types ⋮ A Subexponential Parameterized Algorithm for Proper Interval Completion ⋮ Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions) ⋮ Parameterized complexity of diameter ⋮ Matching cut in graphs with large minimum degree ⋮ Rank Vertex Cover as a Natural Problem for Algebraic Compression ⋮ Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses ⋮ Dynamic programming for graphs on surfaces ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Offensive alliances in graphs ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ Defective Coloring on Classes of Perfect Graphs ⋮ Calculation of Discrepancy Measures and Applications ⋮ Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ Destroying Bicolored $P_3$s by Deleting Few Edges ⋮ On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ Games, Puzzles and Treewidth ⋮ Exploiting $c$-Closure in Kernelization Algorithms for Graph Problems ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Parameterized Algorithms for Power-Efficient Connected Symmetric Wireless Sensor Networks ⋮ On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Known Algorithms for Edge Clique Cover are Probably Optimal ⋮ On the Complexity of Scaffolding Problems: From Cliques to Sparse Graphs ⋮ Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Solving satisfiability in less than \(2^ n\) steps
• Optimization, approximation, and complexity classes
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• On the density of families of sets
• Parity, circuits, and the polynomial-time hierarchy
• An improved exponential-time algorithm for k -SAT
• Algorithms for maximum independent sets
• Finding a Maximum Independent Set
• Worst-case time bounds for coloring and satisfiability problems
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Power indices and easier hard problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Which problems have strongly exponential complexity?