I Computational Complexity

By H. Nader. 2005

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algorithms & Complexity

Citations in the corpus

Community detection in graphs (2009, background): “The class of NP-complete problems has drawn a special attention in computer science, as it includes many famous problems like the Travelling Salesman, Boolean Satisfiability (SAT), Linear Programming, etc. (Garey and Johnson, 1990; Papadimitriou, 1994).”
Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy (2010, unknown): “If A and B are complexity classes, A B denotes the class A with an oracle for B (cf [7, 8] for formal deﬁnitions).”
Algorithms in real algebraic geometry (2003, methodology): “In other words, the existential theory of the reals is in PSPACE [123].”
The price of anarchy of finite congestion games (2005, background): “Furthermore, [22, 4] considered the social cost of maximum latency.”
DTN routing as a resource allocation problem (2007, background): “We can show formally that this reduction is an L-reduction [27].”
Distributed LMS for Consensus-Based In-Network Adaptive Processing (2009, background): “In the eventuality of a sensor failure, determination of a new cycle is an NP-hard problem [14], thus challenging the applicability of incremental schemes in medium- to large-size WSNs.”
Issues in Multiagent Resource Allocation (2006, methodology): “A good starting point for readers interested in the computational approach to Game Theory (and the game-theoretic approach to Computer Science) is the short paper by Papadimitriou [70].”
Optimal Joint Base Station Assignment and Beamforming for Heterogeneous Networks (2014, methodology): “Proof: The NP-hardness proof for the sum-rate utility is based on a polynomial time reduction from the MAX 2-SAT problem [31].”
Classifying the Complexity of Constraints Using Finite Algebras (2005, background): “We remark that the problem CSP({N}) was first shown to be NP-complete by Schaefer [52]; it corresponds to a restricted form of the Not-All-Equal Satisfiability problem [21, 45].”
Approximate Probabilistic Model Checking (2004, background): “Unfortunately, not only are no eﬃcient algorithms known for such counting problems, but they are believed to be strongly intractable (see, for instance [20]).”
Principles of model checking (2008, background): “For the precise definitions and technical details we refer to textbooks on complexity theory, such as [160, 320].”
Quantum computational supremacy (2017, unknown): “46 A basic goal of this theory is to classify problems (such as integer factorisation) into complexity classes (such as the famous classes P and NP ), and then to rigorously prove that these classes are unequal.”