Questions tagged [complexity]
The complexity tag has no usage guidance.
58
questions
-2
votes
1answer
130 views
Evidence integer multiplication is in linear time?
After millenia of quest we have identified two $n$ bit integers can be multiplied in $O(n\log n)$ time. Please refer details in https://www.quantamagazine.org/mathematicians-discover-the-perfect-way-...
10
votes
2answers
2k views
What is a natural problem in theory of computation?
In Stephen Cook's paper on the P vs NP problem,[1] he states the following [2]:
Feasibility Thesis: A natural problem has a feasible algorithm iff it has a polynomial-time algorithm.
My question ...
15
votes
0answers
207 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)}$ ...
8
votes
1answer
346 views
Is convex optimisation in P?
Consider a convex optimisation problem in the form
$$\begin{align}
f_0(x_1, \ldots, x_n) &\to \min \\
f_i(x_1, \ldots, x_n) & \leq 0, \quad i = 1, \ldots, m
\end{align}$$
where $f_0, f_1, \...
1
vote
0answers
63 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, ...
0
votes
0answers
114 views
Oracle separation between PH and PSPACE
I am having difficulty understanding the concept and intuition behind this proof. The proof deals with constructing an oracle $A$ relative to which $PH$ is separated from $PSPACE$.
I have several ...
2
votes
0answers
67 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....
0
votes
0answers
48 views
What is the complexity of Parametric Mixed Integer Linear Programming?
We know
$$\forall\bf y\in\mathbb Z^n:K\bf y\leq b$$
$$\exists\bf x\in\mathbb Z^m:A\bf x + B\bf y\leq c$$
is in $\bf P$ if $n,m$ are fixed from Kannan's result (refer page $1$ in reference).
What is ...
8
votes
0answers
181 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 ...
4
votes
1answer
403 views
Is there a counterexample to this work?
Is there a counterexample to this claim https://arxiv.org/abs/1610.00353? They claim a $O(n^6)$ LP model with simulations to support. I think asking validity is not a reasonable problem. However ...
11
votes
0answers
347 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 ...
6
votes
1answer
205 views
Paths of length $p$ in a Graph, $p$ a prime
I came across the following decision problem, for which I wondered whether anybody of you came across a similar problem and can give me some insight on its nature/complexity.
Given as input a ...
3
votes
0answers
205 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 ...
-1
votes
2answers
482 views
Are these problems in NP class?
${\bf New\ version}$ [Version 1.2]
Let $f: \mathbb{N} \to \{0,1\}$ be a computable function, ${\bf Fin}(\mathbb{Z})$ be the set of all finite subsets of $\mathbb{Z}$, and $W: {\bf Fin}(\mathbb{Z}) \...
0
votes
1answer
129 views
Does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$?
Something has been buzzing me recently. It is well-known that $\textbf{PCP}[poly(n), 0] = \textbf{coRP}$, but does $\textbf{PCP}[poly(n), O(1)] = \textbf{coRP}$ ?
I have found a proof for this ...
2
votes
1answer
105 views
Petri net termination
Termination is the following problem.
Input: a Petri Net with initial marking
Output: "yes" iff there exists an infinite firing sequence. The naive algorithm in the case of bounded nets for example ...
18
votes
1answer
501 views
Formally Verified Complexity Theory
Is there any ongoing project to formally verify the theorems and proofs of complexity theory using a proof assistant like Coq? Are there any boundaries to doing this?
1
vote
1answer
154 views
Complexity of the Schönhage–Strassen algorithm
In the Wikipedia article, the complexity is listed as $O(n \cdot \log (n) \cdot \log (\log (n)))$, where $n$ is the number of bits.
Would the real bound be given by setting $n=\frac{b}{w}$, where $b$...
13
votes
1answer
307 views
Parallel Pebble Game on a Line
In the pebble game on a line there are N+1 nodes labelled 0 through N. The game starts with a pebble on node 0. If there is a pebble on node i, you can add or remove a pebble from node i+1. The goal ...
1
vote
0answers
99 views
How to shrink a very large sparse matrix [closed]
Let $A$ be a matrix where $A \in \mathbb{F}^{n^s \times n^s}$ and $s>2$.
Assume $A$ is a sparse matrix where its rank $\leq n$ and that there is only constant number of non-zero elements in each ...
6
votes
2answers
269 views
Complexity of comparison unary>binary
What is the smallest widely-known complexity class to which
$$\left\{\langle i,j\rangle\middle|\begin{array}{@{}l@{\ }l@{}} & i\ \text{is a unary encoding of a positive integer}\ \hat\imath\\\...
1
vote
1answer
83 views
Why does not the definition of NP problems care about the complexity of guessing? [closed]
I have a question regarding the definition of NP problems. According to that, a problem is in NP if one can guess a certificate of polynomial size in polynomial time. However, this definition does not ...
6
votes
1answer
132 views
What's the complexity of factoring over a set of generators (say in $GL_2$)?
In particular, if I have some char-0 field $k$ (let's take $\mathbb C$ for now) and I consider $G = GL_2(k)$ with arbitrary nontrivial distinct $A, B \in G$. Then for some $C \in GL_2(k)$ do we know ...
3
votes
0answers
74 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. ...
12
votes
2answers
1k views
What exactly are the classes FP, FNP and TFNP?
In his book Computational Complexity, Papadimitriou defines FNP as follows:
Suppose that $L$ is a language in NP. By Proposition 9.1, there is a polynomial-time decidable, polynomially balanced ...
14
votes
2answers
681 views
Are There Highly Symmetric NP- or P-complete Languages?
Does there exist $L$, an NP- or P-complete language which has some family of symmetry groups $G_n$ (or groupoid, but then the algorithmic questions become more open) acting (in polynomial time) on ...
9
votes
2answers
143 views
Complexity of Computing Lexicographically Minimal Element of Orbit
Given strong generators for a group $(G \leq S_n, *)$ acting on bitstrings of length $n$ and an element $s \in \{0, 1\}^n$, how hard is it to compute the lexicographically minimal element of $G.s$, ...
2
votes
2answers
318 views
Formally proving no algorithm exists [closed]
Are there standard techniques to show that no algorithms exist for given complexity constraints?
For example, consider the following problem. The input is a list of items with exactly one duplicate, ...
1
vote
0answers
154 views
Why does this algorithm not have an exponential complexity? [closed]
In this article :
Kinodynamic Motion Planning
B. Donald, P. Xavier, J. Canny, J. Reif
https://www.cs.duke.edu/brd/papers/src-papers/jacm-final.pdf
The authors present a PTAS algorithm that can ...
15
votes
2answers
824 views
Does Karp reducibility yield a total order?
Or with other words, do we have that for every language $A$ and $B$, $A \leq_p B$ or $B \leq_p A$?
5
votes
1answer
147 views
Equivalence for Constant-width Read-Once Branching Programs with Distinct Orders
Let $X={x_1,...,x_n}$ be a set of variables and $\pi:[n]\rightarrow [n]$ be a permutation of the $n$-element set $[n]=\{1,...,n\}$.
A $\pi$-OBDD is an oblivious, read-once branching program where ...
0
votes
1answer
135 views
Why are these two definitions of PLS equivalent?
In the definition of the complexity class $\textsf{PLS}$ we have an algorithm for improving the solutions locally. I have come across the following two definition of such an algorithm.
there is a ...
9
votes
1answer
540 views
2-NEXPTIME-complete problems
We have a problem and we found an algorithm that appear to be 2-nexptime.
I would like to find known 2-nexptime-complete problems in order to find a lower bound.
I found in literature mainly two ...
4
votes
1answer
159 views
Complexity of counting maximum number of co-linear points in Euclidean plane
The problem: given a set of points in the Euclidean plane, find the maximum number of co-linear points.
I already know that the problem can be solved in quadratic time using hashing or projective ...
4
votes
0answers
126 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 "...
10
votes
1answer
243 views
EXP-Complete Problems vs Subexponential Algorithms
Does the fact that a problem $A$ is EXP-time complete implies that $A$ is
not in $DTIME(2^{o(n)})$?
I'm aware that by the time hierarchy theorem, $EXP=DTIME(2^{n^{O(1)}})$ is not
included in $E=...
6
votes
0answers
120 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,...
10
votes
1answer
479 views
Status of PP-completeness of MAJ3SAT
SHORT QUESTION: Is MAJ-3CNF a PP-complete problem under many-one reductions?
LONGER VERSION:
It is well-known that MAJSAT (deciding whether the majority of assignments of propositional sentence ...
0
votes
1answer
192 views
obvious property of big O, big Omega, and big Theta [closed]
I'm trying to determine under what conditions the following statement is true.
The statement is, suppose $f(n) = O[g(n)]$ and $f(n) \neq \Theta[g(n)]$ then $g(n) = \Omega[f(n)]$
where $O$ means "...
6
votes
1answer
209 views
Number of solutions for a system of linear equations over a finite ring
Let $R$ be a finite ring with operations $(+,\cdot)$. Let $A \in R^{m\times n}$ and
$b\in R^{m}$.
Questions:
What is the complexity of counting the number of solutions to the system of equations $...
5
votes
1answer
406 views
How is the VP=VNP question in char 2 different from other char? What is the current frontier in regards to this question?
What are the caveats one should be aware of when pursuing VP=VNP question in char 2 compared to other char? What is the current frontier in regards to this question?
13
votes
2answers
338 views
Collapses under the assumption that $NEXP\subseteq P/Poly$
It is known that if $NP\subseteq P/Poly$ then the polynomial hierarchy collapses to $\Sigma_2^{P}$ and $MA = AM$.
What are the strongest collapses known to happen if $NEXP\subseteq P/Poly$?
-2
votes
1answer
206 views
A variant of the Post Correspondence problem
Given words $\alpha_1, \ldots \alpha_n$ and $\beta_1, \ldots, \beta_n$, Post's Correspondence Problem asks if there is a sequence $i_1, \ldots, i_k$ of indices such that $\alpha_{i_1} \ldots \alpha_{...
9
votes
3answers
564 views
P/Poly vs Uniform Complexity Classes
It is not known whether NEXP is contained in P/poly. Indeed proving that NEXP is not in P/poly would have some applications in derandomization.
What is the smallest uniform class C for which one can ...
5
votes
1answer
116 views
Complexity of propositional LTL with past operators and freeze quantifier?
In "A Really Temporal Logic", by R.Alur and A.Henziger, they introduce an extension of Linear Temporal Logic with a freeze quantifier $x.\phi$, which allows to "give a name" to the current time point ...
1
vote
0answers
85 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 ...
6
votes
1answer
372 views
What is the complexity of vertex cover on k-partite graphs?
Given a k-partite graph which is already partitioned into k parts,
what is the complexity of finding a vertex cover of minimum size?
I guess that it's NP-hard, but couldn't yet prove it or find ...
1
vote
0answers
66 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. ...
2
votes
0answers
189 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 ...
1
vote
0answers
648 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 ...
