Questions tagged [complexity]
The complexity tag has no usage guidance.
31 questions with no upvoted or accepted answers
16
votes
0
answers
281
views
Does small circuits for a NP-complete problem contradict ETH?
The remarks of the Theorem 4 in the paper "On the complexity of circuit satisfiability" claims that: if circuit satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ ...
- 161
11
votes
0
answers
397
views
Error in paper "Some NP-complete geometric problems"?
The paper in question:
M.R. Garey, R.L. Graham and D.S. Johnson. Some NP-complete geometric problems .
This paper proofs the NP-completeness of some well-known problems, such as the Steiner Tree ...
- 275
10
votes
0
answers
161
views
Is 4-Coloring restricted to graphs with crossing number 1 NP-complete?
Planar graphs are 4-colorable.
Determining if a planar graph is 3-colorable is NP-Complete.
A graph with a crossing number 1 (graph such that it can be drawn with $\le 1$ crossing) is 5-colorable.
...
- 109
8
votes
0
answers
229
views
SAT Solvers and their applications
I've been reading and learning about SAT solvers this week. If they can solve problems with thousands of variable quickly haven't we practically solved ANY problem that can be reduced to it, including ...
- 81
7
votes
0
answers
86
views
How is FNP defined? Or, is FNP closed under relaxation?
I hope this isn't a dumb question, but I've been driving myself nuts regarding the following.
The definition of $\mathsf{FNP}$ that I've found in many places is the following:
A relation $R(x,y)$ is ...
- 1,214
6
votes
0
answers
157
views
Complexity of validity of first-order logic over finite words with bounded quantifier alternation?
I'm concerned with the validity problem for sentences of first-order logic over finite words, i.e. $FO[\le]$ interpreted over finite subsets of $\mathbb{N}$. AFAIK it should be nonelementary.
However,...
- 1,698
5
votes
0
answers
126
views
Are there well-accepted attempts of people to create complexity classes in continuous time?
I'm not in CS theory, but I've talked to a complexity theorist recently who, in passing, suggested that my research (not really analog computing, but hypercomputation using physical systems in ...
- 121
5
votes
0
answers
1k
views
Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L
It would be nice to show that $P=L$ implies $NP=NL$. Or, $NP=NL$ implies $UP=UL$. Or maybe, $⊕P = ⊕L$ implies $PP = PL$.
Are there any known connections between the problems: P vs L, UP vs UL, NP ...
- 5,167
4
votes
0
answers
58
views
Reference for cost of translating between regular language formalisms
It is well-known that regular languages can be defined equivalently via many formalisms, among which regular expressions, NFAs, finite monoids, Monadic Second-Order logic (MSO).
The cost (say in size ...
- 9,018
4
votes
0
answers
181
views
Any problems for which we know the complexity, but no algorithms with the same time?
I suddenly found myself wondering if there are any problems for which the complexity (time or space or anything else) is proven, say to be O(n^2), but for which the best known algorithms are worse ...
- 59
4
votes
0
answers
140
views
Natural Problems NSPACE[n] but not in DTIME[n]
It is known that $\mathrm{DTIME}[n]\subseteq \mathrm{DSPACE}[n/\log n]$. Therefore, there are languages in $\mathrm{DSPACE}[n]$ which are not in
$\mathrm{DTIME}[o(n\log n)]$.
Are there examples of "...
- 111
3
votes
0
answers
104
views
Collapse of query and oracle hierarchies
Let ${\tt QH}$ stand for the Query Hierarchy, defined as the union of all classes ${\tt P}^{{\tt NP}[k]}$, of problems solvable by polynomial time machines making at most $k$ queries to ${\tt NP}$ and ...
- 120
3
votes
0
answers
95
views
Complexity of chess with 50-move rule
It is known that evaluating who wins in $n \times n$ chess positions is EXP-complete (and thus unconditionally not in P), and this effect is due to the game having rich possibilities for exponentially ...
3
votes
0
answers
80
views
Extending fagin’s theorem for #P (for arbitary structure)
While i am reading Descriptive complexity of #P functions (Saluja) in theorem 1 he state that #FO coincides #P on ordered structures.
This is a corollary from fagin’s theorem. I have read fagin’s ...
- 139
3
votes
0
answers
829
views
Implications of resolving $BPP$ vs $PSPACE$
The relationship between the complexity classes $BPP$, $P$, and $NEXP$ is currently undetermined. We know that $P \neq EXP$ by the time hierarchy theorem, but we don't know if $BPP = P$ (as many ...
- 199
3
votes
0
answers
90
views
Is there any work that relates the liveness of a Petri Net to the complexity of determining coverability?
I'm working on a problem where the formalism appears to be an abstraction of a kind of Petri net, and it is possible to construct an equivalent Petri net from this formalism with the same behavior. ...
- 139
2
votes
0
answers
72
views
Looking for Research in Cryptographic Computing
I recall reading in college about a nascent research area regarding cryptographic techniques for secure computing, relating to zero-knowledge proofs, but I am having trouble remembering the exact term....
- 473
2
votes
0
answers
229
views
Circuit complexity lower bounds and uniformity
I have troubles to understand how lower bounds w.r.t. circuit complexity and upper bounds w.r.t. uniform machine models can be used to show completeness results.
For example, the word problem for ...
- 31
2
votes
0
answers
55
views
Is there any exsiting research on this kind of "sorting with constraint" problem?
I have been interested in this kind of "sorting with constraint" problem:
Given $n$ items $\{S_1 ,S_2 ,...S_n\}$ with corresponding weight $w_i ,i=1,2,...,n$, we want to sort these $n$ items (i.e. ...
- 439
1
vote
0
answers
83
views
Separating disjoint PSPACE-hard sets by NP-separators (and some variants)
I am trying to find some references or arguments for results of the form, where $X,Y$ vary over complexity classes, typically with $X\subseteq Y$, and $A,B$ are disjoint languages that are $Y$-hard:
...
- 171
1
vote
0
answers
259
views
Cheapest Insertion is $2$-approximation for TSP
Consider the Cheapest Insertion Algorithm on a complete graph with $n$ vertices, where each edge $uv$ has a weight $w(uv)$, and the weights satisfy the triangle inequality $w(xz)\leq w(xy)+w(yz)$ for ...
- 11
1
vote
0
answers
130
views
Deterministic one way communication complexity for message with arbitrary length
Let Alice have a binary string of length $n$ that it wants to send to Bob along a one-bit communication channel. However, Bob does not know the length of the message.
I have been looking into ...
- 11
1
vote
0
answers
378
views
What is the computational complexity of the fastest algorithm to compute Jordan canonical form for a matrix
Given a matrix, What is the computational complexity of the fastest algorithm to compute Jordan canonical form for the matrix? suppose the value of elements of the matrix and eigenvalue are complex ...
- 1,071
1
vote
0
answers
75
views
Sentences in what kinds of grammar in the Chomsky hierarchy can be parsed by an LSTM of a given size?
Given
an LSTM $N$ of a given size $A$,
a sentence $S$ with a given number of words $B$,
a Chomsky grammar hierarchy level $C$ in 0-3,
a Chomsky grammar $G$ of level $C$ of size $D$,
A given fixed, ...
- 107
1
vote
0
answers
95
views
Complexity of Maximum Independent Set (or Vertex Cover) on disk packing graphs
I'm interested in complexity results for Maximum Independent Set (or Vertex Cover) problem over the class of disk packing graphs. Having a set of disks we build a graph that has its vertices at the ...
- 111
1
vote
0
answers
71
views
Equivalent SDP problems different solving times
I have two SDP problems which are proved to be equivalent (in terms of optimal objective values) to each other in theory. Moreover, they have same number of constraints and variables respectively. ...
1
vote
0
answers
666
views
Is there any theory that allows to compute the computational complexity boundaries like this?
I recently had an interview, at which I was asked to solve the following problem: you have a sorted array of integers, and you need to find if there are 3 numbers that sum to 0. The brute force ...
- 119
0
votes
0
answers
13
views
Regret bound of returned policies
I encountered a proof in the paper Imitation Projected Programmatic Reinforcement Learning that I find puzzling.
In particular, it is Theorem A.2 in the appendix, in the section of Bounding relative ...
0
votes
0
answers
105
views
Complexity of Identifying SAT Problems with a Unique Solution from Satisfiable Instances
I am curious about the computational complexity involved in identifying SAT problems that have only one solution from a set of satisfiable SAT instances.
input and output: input: A satisfiable cnf ...
- 388
0
votes
0
answers
39
views
Hardness of finding minimal subsets that will change the maximum of a univariate polynomial
Given a univariate polynomial of the form $p(x) = \prod_{0 \leq i \leq N}{(x*a_i + b_i)}$ when all of the $a_i$ and $b_i$ are numbers in the range [-1,1] and $i$ goes from $0$ to $N$ (we are given all ...
- 11
0
votes
0
answers
302
views
Complexity of multi-objective optimization problems
How can we define and prove the worst-case complexity of multi-objective optimization problems (MOOP)?
It is easy to see that, if one of the objectives is an NP-Hard optimization problem, then the ...
- 185