Questions tagged [complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers
72 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 ...
0 votes
0 answers
56 views

Is there some intuitive point to understand Co-NP/poly?

I know what it means: The coNP/poly problems are problems that decide a problem in co-nondeterministic poly-time using a $poly(n)$-size advice, where $n$ is the input size. By the definition, we have ...
  • 9
-2 votes
0 answers
78 views

What is the hardness of the following problem?

Input: Given a set on $V$, and for each subset $X \subseteq V$, there is a map $f: 2^V \rightarrow \mathbb{Z}_+$ (nonnegative integer). Output: find a partition of $V$ such that $f(S) + f(V- S)$ is ...
  • 9
4 votes
0 answers
51 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 ...
  • 8,223
5 votes
0 answers
114 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 ...
1 vote
0 answers
140 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 ...
0 votes
0 answers
110 views

Direct fpt reduction from Weighted 3SAT to Weighted 2SAT

In parameterized complexity, for each fixed $q$, the problem Weighted $q$-CNF SAT is W[1]-complete. In particular, this means that one can turn a 3CNF formula $\varphi$ into a 2CNF formula $\varphi'$ ...
9 votes
1 answer
141 views

Validity problem of intuitionistic two-variable logic

The two-variable fragment $\mathrm{FO}^2$ consist of those sentences of first-order logic $\mathrm{FO}$ in which precisely two variables occur (e.g. $\exists x \exists y \exists z R(x,y,z)$ is not a ...
4 votes
0 answers
179 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
3 votes
1 answer
95 views

Recursive generic oracles

In Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide, An oracle builder’s toolkit, Inf. Comput. 182, No. 2, 95-136 (2003). ZBL1025.68041, the authors go through a variety of generic oracles. ...
1 vote
1 answer
158 views

Is QMA known to contain Co-NP?

Is QMA known to contain Co-NP? If not, would Co-NP being contained in QMA have any implications for other complexity classes. (e.g. Causing the polynomial heirachy to collapse.)
6 votes
1 answer
252 views

What is the impact of encodings of sparse structures on the complexity of the model checking problem?

Some preliminaries first. Consider a purely-relational structure (a.k.a. database) $\mathfrak{A} = (A, R_1^{\mathfrak{A}}, \ldots, R_{|\tau|}^{\mathfrak{A}})$ over some finite signature $\tau = \{ R_1,...
2 votes
1 answer
78 views

Relative error estimation of a special type of GapP function

Consider the functions included in the complexity class GapP. We know that approximating a function from GapP, in the worst case, to inverse polynomial multiplicative error, is #P-hard. Even correctly ...
  • 163
1 vote
0 answers
120 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
0 answers
256 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 ...
5 votes
1 answer
138 views

Different definitions of grammar complexity

It's known that there are different "kinds" of grammar complexity of language $L$ --- nonterminal complexity (minimal possible $|N|$ for grammar $(N, \Sigma, P, S)$ generating $L$), covering ...
  • 411
8 votes
1 answer
159 views

Generating a pseudo random Rubik's cube in $O(n^{2+\epsilon})$ time

Recently I've begun considering how one could generate and solve an $n \times n\times n$ Rubik's cube for $n$ well over 10,000. To solve such a cube is feasible; easily implementable parallelizable ...
3 votes
1 answer
134 views

CNF encoding of set cover - NExpTime-completness

Notation: given a CNF formula A over variables X, we write $[A(X)]$ for the set of valuations $v: X \to \{0,1\}$ such that $A(X/v)$ is true, i.e. the set of valuations that makes formula A true. I ...
9 votes
0 answers
142 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. ...
1 vote
1 answer
97 views

Is there significance to the ratio of the time it takes to locate a problem's solution over the time it takes to verify the solution?

I believe I have found a problem, the solution to which can be verified in 0 time (the solution can only be located in non-zero time, however). As a result, the ratio of the time required to locate a ...
6 votes
2 answers
387 views

On the complexity of a "list" datastructure in the RAM model

I am interested in the complexity of a data-structure equipped with the following operations (similar to a list): insertion of an element at a given position within the list deletion of an element at ...
  • 775
10 votes
1 answer
405 views

The theoretical complexity of Go - The state of the art

What are the latest advances in theoretical complexity of Go? I know some early works about the complexity of Go: "Go is polynomial-space hard" proved that Go is PSPACE-hard. "Ladders are PSPACE-...
  • 405
0 votes
0 answers
198 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 ...
0 votes
2 answers
163 views

Fast algorithm to find pair of triangles with a common edge in a complete graph

Suppose we have a complete graph with 4 nodes. To each triangle in this graph we assign a value $energy$ that is the multiplication of its edge weights. The question is to first find pair of triangles ...
8 votes
4 answers
669 views

Constraints on sliding windows

Let $L\subseteq \Sigma^*$ be a language of finite words and $n>0$ some integer. I would like to know if anything is known on the time and space complexity with respect to $n$ to check for ...
  • 992
-1 votes
1 answer
215 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-...
  • 12.6k
12 votes
2 answers
3k 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
0 answers
269 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)}$ ...
  • 151
9 votes
1 answer
1k 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
0 answers
73 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, ...
2 votes
0 answers
71 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....
8 votes
0 answers
198 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 ...
5 votes
1 answer
445 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 ...
  • 12.6k
11 votes
0 answers
384 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
1 answer
222 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 ...
  • 61
3 votes
0 answers
692 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
2 answers
1k 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}) \...
  • 7
0 votes
1 answer
168 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 ...
  • 13
2 votes
1 answer
226 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 ...
  • 91
27 votes
2 answers
851 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
1 answer
372 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$...
  • 21
15 votes
1 answer
392 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,478
1 vote
0 answers
114 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
2 answers
560 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\\\...
user avatar
1 vote
1 answer
152 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 ...
  • 27
6 votes
1 answer
141 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
0 answers
84 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. ...
15 votes
2 answers
3k 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 ...
  • 283
14 votes
2 answers
739 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
2 answers
171 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$, ...