Questions tagged [complexity]

The tag has no usage guidance.

20 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
15
votes
0answers
246 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)}$ ...
11
votes
0answers
371 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 ...
9
votes
0answers
133 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. ...
8
votes
0answers
191 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 ...
6
votes
0answers
133 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,...
5
votes
0answers
859 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 ...
4
votes
0answers
133 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 "...
3
votes
0answers
138 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 ...
3
votes
0answers
493 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 ...
3
votes
0answers
80 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. ...
2
votes
0answers
68 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....
2
votes
0answers
197 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 ...
2
votes
0answers
49 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. ...
1
vote
0answers
105 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 ...
1
vote
0answers
179 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
vote
0answers
70 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, ...
1
vote
0answers
93 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 ...
1
vote
0answers
67 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
0answers
661 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 ...
0
votes
0answers
115 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 ...