# Questions tagged [computational-complexity]

This is a branch that includes: computational complexity theory; complexity classes, NP-completeness and other completeness concepts; oracle analogues of complexity classes; complexity-theoretic computational models; regular languages; context-free languages; Komolgorov Complexity and so on.

1,092 questions
Filter by
Sorted by
Tagged with
131 views

### Algorithmically decide if an algorithm has optimal time complexity [closed]

Is there an algorithm with the following input and output? INPUT: an algorithm computing a function $\mathbb{N}\to\mathbb{N}$. The algorithm is guaranteed to halt on all inputs. OUTPUT: "YES"...
118 views

### What is the complexity class of this problem without Cramer's conjecture?

The problem 'Given $0<a<b$ is there a prime in the interval $[a,b]$?' is in $\mathsf{NP}$. If we assume Cramer's conjecture the problem is in $\mathsf{P}$ since if $b-a>(\log a)^{2+\epsilon}$ ...
113 views

### Bi-Hölder embeddings of finite metric spaces

This is a reference request. There is a large body of work, I'm familiar with, that describes the existence of bi-Hölder embeddings of finite metric spaces into Euclidean space (such as this ...
54 views

### What are the complexity classes of these problems about divisibility and coprimality?

The problems 'Given $0<a<b$ and a prime $p<a$ is there an integer $\ell\in[a,b]$ such that $p|\ell$?' 'Given $0<a<b$ and an integer $q\not\in[a,b]$ is there an integer $\ell\in[a,b]$ ...
933 views

### Determining if a rational function has a subtraction-free expression

This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class. Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...
155 views

### Maximize sum of edge weights on spanning tree

Problem: Given a complete graph with n vertices, the edge weight between vertex $i$ and vertex $j$ is $b[i]\times b[j]$. Under the condition that the degree of point $i$ on spanning tree is DEG $[i]$, ...
65 views

### Complexity of polynomial inequalities

What is known about the complexity of deciding whether a finite set of polynomial inequalities in $n$ real variables with integer coefficients is satisfiable? Decidability is guaranteed by Tarski's ...
88 views

### Are there any neusis-hard/neusis-complete problems?

I have lately been enjoying Richeson's Tales of Impossibility (see MAA review), an accessible book on the famous problems of Euclidean geometry including angle trisection/cube doubling/heptagon ...
900 views

86 views

### Is the graph minicut with the node cardinality constraint NP-hard?

I wonder whether the following problem is a well-studied NP-hard problem? Get a graph $G$ and a number $k$, we partition the graph $G$ into two components where each component should have at most $k$ ...
43 views

### Reduction graph isomorphism to maximum independent set in very dense graph

We got a reduction graph isomorphism to MIS in a very dense graph, or alternatively negative monotone 2-CNF to MAX-ONEs with a formula with many clauses. Let $G,H$ be graphs of order $n$ and adjacency ...
89 views

The Kolmogorov-Arnold representation theorem says, essentially, that when computing a continuous function, the only multivariate function you really need is addition. (Somewhat) more precisely, it ...
714 views

### Complexity of solving systems of linear diophantine equations

It is "well known" that a matrix system $Ax=b$ where $A\in \Bbb Z^{m\times n}$, $x\in \Bbb Z^n,b\in\Bbb Z^m$ for some $m,n \in \Bbb N$, can be solved in polynomial time, using Smith/Hermite Normal ...
61 views

### Isomorphism preserving transformation graph to graph of logarithmic boolean width and bounded degeneracy

The paper On graph classes with logarithmic boolean-width claims that some graph problems are fixed parameter tractable with parameter the boolean width. In particular, boolean-width of the complement ...
612 views

### Complexity of counting words of given length in regular or context-free language

Let $L$ be a regular or context-free language over alphabet $\{0,1\}$. What is the complexity of counting words of length $n$ in $L$? Is it possible to efficiently find if for given $n$ all words ...
155 views

### Reference: Packing under translation is in NP

I am looking for a reference for a result that I am aware of. Let me describe the result. Given a polygon $C$ and polygons $p_1,\ldots,p_n$, it can be decided in NP time, if $p_1,\ldots,p_n$ can be ...
104 views

### Complexity of solving $\sum_i A_i X B_i = C$

Is anything known about computational complexity of finding $X$ which satisfies the following matrix equation? $$\sum_i^n A_i X B_i = C$$ With $A_i,B_i,C$ dense $d\times d$ matrices. Any literature ...
88 views

### Can equality of chromatic symmetric functions of two trees be checked in polynomial time?

Stanley defined chromatic symmetric functions (CSF) in 1995 (Advances in Math) where he conjectured that trees can be distinguished by their CSF. However, tree isomorphism is decidable in P (...
224 views

462 views

### Is strictly harder than NP-hard cryptography possible?

Looks like there is cryptography based on NP-hard problem, e.g. McEliece cryptosystem. The algorithm is an asymmetric encryption algorithm and is based on the hardness of decoding a general linear ...
830 views

### Can we solve Hamiltonian Path problem for biconnected planar graphs in linear time?

Assume that we have a bi-connected planar graph $G$ with $\Delta(G)>3$, and we want to find a Hamiltonian Path in $G$. As we know the st-order of a bi-connected planar graph can be computed in ...
55 views

### Polynomial time for a quadratic equation and linear inequalities?

Does anyone know how to find a feasible solution (or the infeasibility of any solution) in a polynomial time to the following problem: \begin{align*} xAx^t = 0, \\ Bx^t = c, \\ x_i \ge 0, \end{align*} ...
79 views

### What it is wrong with the proof $PH = AM = coAM$ based on FORMULA ISOMORPHISM?

Confusion is possible, but Emil's comment and a paper imply major result: collapse of the polynomial hierarchy. Q1 What is wrong with the proof that $PH = AM = coAM$ given below? In a comment about ...
207 views

### Can we make cryptography signature algorithm based on hardness of isomorphism?

In public key cryptography, Alice knows functions $f$ and its inverse $f^{-1}$. $f$ is public and $f^{-1}$ is secret. To sign a message $m$, she gives $(m,a=f^{-1}(m))$. To verify a signature, the ...
404 views

### Finite objects for which isomorphism is NP-hard or harder?

Are there finite objects for which deciding isomorphism is NP-hard or harder? Graphs and groups are not solutions. Searching the web didn't return answer for me. Partial result based on Chow's ...
505 views

### Graph classes where Hamiltonian Cycle and Hamiltonian Path problems have different complexity

While searching The information System on Graph Classes and their Inclusions, I stumbled on several graph classes for which the Hamiltonian Cycle problem is $NP$-complete while the complexity of ...
42 views

### Can you efficiently solve a linear system with a quadratic multivariate polynomial of degree 2?

Given a system of linear equations, $P=\{p_1,\dots,p_m-1\}$ and a $2$nd degree polynomial $p_m$ where $p_i: \mathbb{R}^n \rightarrow \mathbb{R},$ can you efficiently find a common zero of all of these ...
### Does $\mathsf{Q}$ have any interesting provably recursive functions?
This question was asked and bountied at MSE without success. For an appropriate theory $T$, say that an $n$-ary $T$-provably recursive function is a $\Sigma_1$ formula $\varphi$ with $n+1$ free ...
Given a graph $G=(V,E)$ and a pair of source-destination nodes $s$ and $t$. Time is divided in periods with the total number of periods denoted by $T$. Each edge $e$ is either operational or broken at ...