Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
2,944
questions
33
votes
12
answers
5k
views
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
This is somewhat of a meta-cstheory question, and is more historical in nature. What are some good examples of problems for which the literature followed the develpment below:
The original algorithms,...
- 331
2
votes
0
answers
95
views
Does the awards budget cut problem support a sub $O(n\log n)$ time solution?
There's a famous problem these days in the interview prep community (particularly in PRAMP) called the awards budget cut problem.
The problem gives you an input of $n$ integers called grants $g_1 ... ...
- 369
1
vote
0
answers
55
views
Complexity Lower Bounds for 3D Sparse Gaussian Elimination
I'm interested in lower bounds on the complexity in the real-RAM model of solving systems of linear equations which have the sparsity pattern of a three-dimensional cubic mesh. Specifically, consider ...
- 111
-4
votes
1
answer
27
views
Help find algorithm for array-based task
Given array if numbers a[1..n]. Pair of numbers (i, j) is interesting, if i < j и a[i] > 2a[j]. How to count number of interesting pairs in O(nlogn)?
What is the solution?
My solution is not ...
- 11
12
votes
0
answers
352
views
NP complete problem help
I'm currently trying to find a reduction to this problem:
Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...
- 121
1
vote
0
answers
78
views
Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains
Let ${\cal L}=\{Y_1,..., Y_k, X\}$ be a finite relational language such that $X$ is a unary relation name. Let $\phi(X,\bar{Y})\in{\cal L}$ be a first-order formula (the formula can have the equality ...
- 322
1
vote
0
answers
216
views
Is there a known lower-bound on what the exponent could be, even if it turned out that P=NP?
Underlying motivation for the question: if someone showed that $\text{P}=\text{NP}$ but the algorithm thus produced for, e.g., $3\text{-SAT}$, runs in time $\Omega(n^G)$ where $G$ is Graham's number, ...
- 1,510
2
votes
1
answer
129
views
Computational complexity problem book with solution recommendation?
I will be taking complexity class next quarter and we will use the book "B. Barak, S. Arora, Computational Complexity: A Modern Approach". However, I have little exposure to complexity ...
- 41
10
votes
0
answers
175
views
Provable BPP Hierarchy
No Time Hierarchy theorem is known for $\mathsf{BPTIME}$, however, consider the following simple modification of the definition:
A language is in $\mathsf{ProvableBPTIME}[f(n)]$ if there is a ...
- 13.8k
5
votes
2
answers
257
views
Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?
Since $e$ is transcendental, the function $f:\mathbb Z_{\geq 0}^{n+1}\to \mathbb R$ is injective,
$$ f(\underset{\text{Integers}\ \geq\ 0}{\underbrace{a_0,a_1,\ldots, a_n}}) = a_0 + a_1e+a_2e^2+\cdots ...
- 1,879
1
vote
0
answers
52
views
Living in Minicrypt, but sampling hard instances without the solution
In Impagliazzo's worlds, Minicrypt is the one, where one way functions exist.
In other words, we can sample hard-on-average instances of NP complete problems.
Question:
Is living in Minicrypt, where ...
- 197
1
vote
1
answer
136
views
Complexity of a satisfiability problem
I would like the know the complexity of a specific satisfiability problem. I have a feeling it could be solved in polynomial time, but I am not sure about it. The problem is described below.
Given $n$ ...
- 13
2
votes
1
answer
138
views
Complexity of MAX-ONEs Monotone 2-SAT with $n^{3/2}$ or $C n^2$ clauses?
Let $\phi$ be negative monotone 2-CNF on $n$ variables and $n^{3/2}$
clauses.
What is the complexity of finding satisfying assignment with maximum
number of ones $k$?
Alternatively let $G$ be a graph ...
- 1,955
3
votes
0
answers
141
views
If $\sf{E} = \sf{NE}$. Then $\sf{NP}-{P}$ contains no sparse sets [closed]
I am reading "The Complexity Companion" by Hemaspaandra & Ogihara, I have a question about lemma 1.21.
In its proof, they suppose $L$ is some sparse language in $\sf{NP}$ ($||L^{=n}||&...
- 139
29
votes
3
answers
3k
views
Is Descriptive Complexity dead?
I recently started reading about Descriptive Complexity, the branch of Complexity Theory studying the logic languages needed to express complexity classes. The main milestone in the area seems to be ...
- 547
6
votes
1
answer
254
views
Are all computational models of quantum computing equivalent?
So the question was inspired by a seminar which presented the following models of quantum computing:
Quantum Computing with Photons
Quantum Computing with Rydberg atoms
Quantum Computing with trapped ...
- 706
0
votes
0
answers
85
views
Is the traveling salesman problem still NP-hard if all edges need to be covered as well?
If we formulate the travelling salesman problem with an added edge-covering constraint as follows, is it still NP-hard?
Given a graph G with non-negative edge weights, is there a circular walk in G ...
0
votes
1
answer
73
views
How hard is deciding the existence of a polygonization with prescribed perimeter?
Polygonization problem of a set of points in the Euclidean plane (2D lattice) is to find a simple polygon that passes through all points. Deciding the existence of a polygonization with minimum (or ...
- 20.7k
8
votes
1
answer
339
views
On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$
It has been shown in [1] that $k\text{-SAT}$ has a $2^{o(n)}$ algorithm if and only if it has a $2^{o(m)}$ algorithm, $n$ being the number of variables and $m$ being the number of clauses.
Being $s_k=\...
- 6,665
6
votes
1
answer
268
views
Why does Dinur's proof of the PCP theorem fail to work for unique games?
What is the critical step where things go wrong if one attempts to use Dinur's proof the PCP theorem to prove the unique games conjecture by starting from a unique label cover instance and doing gap ...
- 61
1
vote
0
answers
66
views
Some examples of tools to demonstrate problem is in $NC$ [closed]
Unlike the class $P$ or $NP$ the class $NC$ does not have any complete problems. To show a problem is in $NC$ one needs to marshal efforts to directly show the problem is in $NC$ since there are no ...
- 12.6k
0
votes
0
answers
52
views
How and How fast can we infer a logical formula that expresses a given graph in C$^2$( logic with 2 vars and counting quantifiers)?
In the following paper the author's claim that almost all graphs can be expressed in first order logic with counting quantifiers and two variables.
I would like to know, is there any algorithm that ...
- 706
14
votes
1
answer
1k
views
Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?
Question: Are there languages decidable in linear time by RAM machines that have superlinear time complexity lower bounds for Multitape Turing machines?
Background: I recently stumbled upon the ...
- 5,005
8
votes
1
answer
235
views
Is there any online lecture series that covers "Computational Complexity: A Modern Approach"?
I am trying to cover the Computational Complexity :A Modern approach by Boaz Borak and Sanjeev Arora. Are there any nice lecture series that cover this material ?
- 706
6
votes
0
answers
373
views
On an unsubstantiated number in a proof of a weaker PCP theorem
I am a mathematician studying Arora and Barak's textbook Computational Complexity, and I am having trouble following one detail in their proof of this weaker PCP theorem:
Theorem 11.19. We have NP $\...
- 265
-2
votes
1
answer
171
views
How to calculate complexity in a high dimensional space?
Edit: 'Fitness landscape analysis' was mentioned as a relevant measure. If you're going to downvote the post, at least leave a comment what is wrong.
For a specific f(), I'm defining a term '...
- 55
10
votes
1
answer
314
views
On the usage of Arora and Barak's main lemma in their proof of the PCP theorem
I am a mathematician working toward understanding a proof the the PCP theorem using Arora and Barak's textbook Computational Complexity. I believe I found a few (fixable) errors in Section 22.2, in ...
- 265
7
votes
0
answers
192
views
Reference for computing the rank of a matrix in polynomial time
In a recent paper, I need to use the fact that computing the rank of a matrix over the integers has polynomial complexity. Given the context, I don't particularly care about the exact asymptotics, as ...
- 171
19
votes
1
answer
1k
views
Has parameterized complexity led to better algorithms?
I know that for the vertex cover problem, if we know that the parameter $k$ (which is the number of vertices in the solution) is small, then we can expect to solve it feasibly in practice. So far, ...
- 301
9
votes
1
answer
411
views
Complexity Theory Consequences of $\mathsf{NP} = \mathsf{QP}$
I have a certain impossibility result that holds unless $\mathsf{NP} = \mathsf{QP}$. It seems quite likely that one could strengthen this to hold unless $\mathsf{NP} = \mathsf{P}$, which I would not ...
- 778
2
votes
1
answer
220
views
Is it possible to reduce an NP language to a NEXP language with exponentially smaller input length?
Suppose we have an NP-complete language $L_1$ and a NEXP-complete language $L_2$.
For any deterministic exptime machine $M_1$ with oracle access $M_1^{L_1}$, is it possible to find a deterministic ...
- 383
4
votes
0
answers
89
views
Complexity of Encoding a Matroid Flow Problem in a Matrix
Context:
Take a directed graph $G$ with a specified subset of source vertices $S$ and target vertices $T$.
We say a subset $I\subseteq T$ of size $r$ is independent if there exist $r$ distinct ...
- 464
2
votes
0
answers
167
views
Complexity of Edge Coloring Regular Graphs With Large Degrees
There is an interesting series of papers on edge colorability / $1$-factorization of regular graphs with large degrees, which over the years have shown better and better lower bounds for the degree $\...
- 21
4
votes
1
answer
295
views
Proof of $LP$ is in $coNP$ without showing it is in $P$?
Is there a proof that linear programming is in $coNP$ without showing it is in $P$?
If so what is the strategy?
- 12.6k
1
vote
1
answer
115
views
Common solutions to 3SAT and 2SAT models comprised of the same variables
I have a problem which is a combination of 3SAT & 2SAT instances.
Consider $L$ is a set of variables $(x_1 ... x_n)$. $S_3(L)$ is a 3-SAT instance and $S_2(L)$ is a 2SAT instance, both made of ...
- 41
7
votes
1
answer
245
views
Isomorphism of ‘ordered’ DAGs / acyclic semiautomata
I am wondering what is known about the isomorphism problem on ordered DAGs, in particular how to find a canonical representative modulo isomorphism.
By ordered I mean that each vertex has a list of ...
- 203
6
votes
0
answers
137
views
Separating QMA and QCMA
A separation between $QMA$ and $QCMA$ remains a notoriously difficult open problem. Even an oracle separation remains elusive. Have there been any recent efforts towards establishing such a separation,...
- 163
1
vote
0
answers
60
views
Complement of Multi-colored Clique with an extra condition
In the problem Multi-colored clique, we ask for a $k$-clique of the input graph $G$ where $G$ is guaranteed to be $k$-colorable. In the complement problem Independent Set given Clique Partition, we ...
- 1,633
2
votes
1
answer
197
views
Complexity of Multi-colored Clique when every color pair induce biclique+isolated vertices
I am interested in the MulitColoredClique problem with an additional restriction.
(Def.: A $k$-coloring $V_1,V_2,\dots,V_k$ of a graph $G$ is a partition of the vertex set of $G$ into $k$ independent ...
- 1,633
6
votes
0
answers
121
views
Computational complexity of finding paths with specified product in a (group-labeled) directed graph
This question came up in the analysis of the puzzle game Swish. One way of representing the solvability problem is this: given a directed graph $G$ where each edge of the graph is labeled with an ...
- 1,346
13
votes
1
answer
478
views
Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
In this talk at the Simons Institute, Holger Dell notes that there is a parsimonious reduction from 3-SAT to the 3-dimensional Matching (3-DM) problem. In other words, there is a reduction between ...
- 464
1
vote
0
answers
73
views
Can the theory of Bidimensionality be applied to weighted instances of a problem?
So my understanding of bidimensionality is you are assured the problem solution is about O(k^2) so you can pay O(k) purely to reduce the instance to one of bounded treewidth. As far as I know, this ...
- 227
1
vote
0
answers
108
views
On proving the standard $p$-measure on $NP$ assumption?
In the answer here An Anthology of Complexity Assumptions an interesting assumption is made. The assumption is $p$-measure of $NP$ is not $0$. There are many non-trivial consequences that follow from ...
- 12.6k
1
vote
1
answer
103
views
Consequences of turning $\oplus \text{SAT}$ into few satisfying assignments
Suppose there is a reduction which, given a $\oplus \text{SAT}$ instance $\phi$, returns another $\oplus \text{SAT}$ instance $\psi$ having all the following properties:
The size of $\psi$ is ...
- 6,665
-3
votes
1
answer
71
views
tables of reductions in literature [closed]
I'm interested in tables of which problems are reducible to which other problems. Particularly for graph problems, but any such tables/graphs would be neat, just so I know how to look for them. ...
- 113
1
vote
0
answers
233
views
Disproving $\oplus$ETH by reducing $\oplus k$-SAT with $n$ variables and $m$ clauses to planar graph with $o(m^2)$ vertices?
In this question and its answer, they discuss about reducing CNF-SAT with $n$ variables and $m$ clauses to a (problem on) planar graph $G=(V,E)$ with $|V|$ as small as possible. It is said that the ...
- 6,665
6
votes
0
answers
116
views
Counting on grid graphs
Are there problems defined on graphs, such as counting 2-factors, Hamiltonian cycles, connected spanning subgraphs etc., that are in $\#P$ and remain hard for grid graphs?
Since there seem to be ...
- 748
22
votes
3
answers
6k
views
Implications of proving NP=RP on complexity theory
Edit: As indicated below by Mahdi Cheraghchi and in the comments, the paper has been withdrawn. Thanks for the multiple excellent answers on the implications of this claim. I, and hopefully others, ...
- 2,039
2
votes
0
answers
53
views
The Edge Cover Equilibrium Problem
Let the Edge Cover Equilibrium Problem be the following:
INPUT: a simple undirected graph $G$.
OUTPUT:
YES, if the number of edge covers of $G$ having odd cardinality is equal to the number of edge ...
- 6,665
4
votes
0
answers
88
views
Complexity of finding the mean of the subset with smallest variance
Let $x_1,\ldots, x_n \in R^d$, and $\alpha \in (0, 1)$. Suppose that $\alpha n$ is an integer.
Let's consider the following problem
$\min_{\mu \in R^d} \frac{1}{n} \sum_{i=1}^n F\left(\frac{\pi(i)}{n}\...
- 181