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.

Filter by
Sorted by
Tagged with
0
votes
1answer
129 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"...
0
votes
1answer
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]$ ...
3
votes
0answers
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}$ ...
0
votes
1answer
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]$, ...
1
vote
0answers
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 ...
5
votes
0answers
86 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 ...
8
votes
0answers
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 ...
4
votes
0answers
127 views

Games and the right mathematical framework for GANs

Generative Adversarial Networks were introduced in http://papers.nips.cc/paper/5423-generative-adversarial-nets and has more than 20000 citations. It is an important topic within deep learning. Are ...
0
votes
0answers
34 views

Hardness of generating Gaussian distribution

I would like to ask about the computational complexity of the problem of generating integers so that the obtained distribution is asymptotic to the Gaussian distribution. Any related reference is very ...
0
votes
0answers
54 views

Computing Partial Theta Series

Let $x\in [-1,1]$ and $\sigma \le 1$. For a certain application we need to compute $\sum_{j\ge 1}(-1)^{j-1}\exp\bigg(-\frac{j^2+2xj}{2\sigma^2}\bigg)$ to within an $\epsilon$-additive error. How fast ...
10
votes
1answer
577 views

What is known in general about the liquid transfer problem?

In several puzzle books, I have seen the following kind of a problem: there are several containers that can hold up to certain amounts of liquid (these liquids are assumed to be infinitely divisible). ...
1
vote
0answers
27 views

what is the computational complexity of Louvain algorithm?

I am not able to find out the computational complexity of the Louvain Algorithm. Can anyone here help me? link of the paper given below: DOI: 10.1088/1742-5468/2008/10/P10008 https://doi.org/10.1038/...
3
votes
0answers
104 views

Creating an $n\times n$ grid with specified $2\times2$ sums [closed]

Suppose we have an $(n-1) \times (n-1)$ grid $A$ with numbers in each cell. How can we efficiently create a new $n \times n$ grid $B$ of digits where each $A_{i,j}$ is the sum of the corresponding $2\...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
3
votes
0answers
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 (...
0
votes
2answers
74 views

Optimal path with multiple costs

Given a graph $G=(V,E)$, each edge $e$ has $k$ costs $c_i(e)$, $1\le i\le k$. Correspondingly, a path $P$ is also characterized by $k$ costs where $c_i(P)=\sum_{e\in P} c_i(e)$. Given vertices $s$ and ...
1
vote
1answer
83 views

Exact volume calculation of a polytope is NP hard under which restrictions?

Computing the exact volume of a polytope given in half space representation seems to be NP-hard. One paper I found proved it is hard for rational coefficients. (However, the paper itself was behind a ...
3
votes
0answers
43 views

Reference: Asymptotic bit-complexity of algebraic operations and transcendental functions

This question is a reference request. Does anyone know of a reference that lists the asymptotic bit-complexity of algebraic operations and transcendental functions implemented on a Turing machine that ...
2
votes
0answers
96 views

Two from cubic subgraph hardness

The Problem For a given graph $G$, the cubic subgraph problem asks if there is a subgraph where every vertex has degree 3. The cubic subgraph problem is NP-hard even in bipartite planar graphs with ...
2
votes
1answer
137 views

On the computational complexity of Pepin's test

Let $F_{n} = 2^{2^{n}} + 1$, where $n > 0$. Pepin's Test asserts that $F_{n}$ is prime if and only if $F_{n} \mid 3^{\frac{F_{n} - 1}{2}} + 1$. QUESTION: What is the big-$\mathcal O$ complexity of ...
2
votes
0answers
21 views

Algorithm for lightest unnested planar vertex-disjoint cycle-cover

Question: given a finite set $\mathcal{P}$ of disjoint points in the Euclidean plane and the set $\mathcal{C}$ of all simple polygons whose corners are subsets of $\mathcal{P}$, what is the ...
3
votes
0answers
27 views

Restriction of Rademacher Complexity

Let $F\subseteq C([0,1]^n,\mathbb{R})$ be a finite family of functions, which is non-empty. Let $A,B$ be subseteq of $[0,1]^n$, again non-empty, and let $Rad(C)$ denote the Rademacher complexity of ...
3
votes
1answer
252 views

What is the big-O time complexity of computing $1/N$ to $\log_{2}(N)$ bits of precision?

I am considering large integer values of $N$ (100 or more digits in base-$10$). In my algorithm, I need to be able to compute the reciprocal of $N$ with enough precision that the repetend will have ...
3
votes
1answer
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 ...
1
vote
0answers
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*} ...
0
votes
0answers
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 ...
4
votes
0answers
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 ...
0
votes
0answers
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 ...
4
votes
0answers
171 views

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 ...
4
votes
0answers
146 views

Disjoint paths in temporal graphs

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 ...
11
votes
1answer
716 views

How did the Baker-Gill-Solovay paper come to be?

How did the Baker-Gill-Solovay paper come to be? Why were those three people talking together about "Relativizations of the $P=?NP$" question, and what was their collaboration like for the ...
2
votes
0answers
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 ...
4
votes
1answer
179 views

NP-hardness of a sequence problem

Given $n$ binary sequences $s_i$ ($1\le i\le n$) with common period $T$. Let $s_i^{t_i}$ denote the sequence obtained by cyclically shifting $s_i$ for $t_i$ bits. The $n$ sequences form a good system ...
1
vote
0answers
38 views

Meaning of L-reduction from Dominating set problem

We are working in a variation of Locating dominating sets. Recently, we realized that the reduction from dominating set to our problem in proving its NP-completeness turns out to be also an L-...
1
vote
0answers
121 views

Checking existence of proofs of fixed length

This question is a continuation of a related previous question (check here). Let $\mathcal{L}$ be a recursive first-order theory with the Hilbert-Ackerman's proof calculus, and such that the ...
4
votes
1answer
190 views

Computational complexity of proof verification

Let $\mathcal{L}$ be a recursive first-order theory, with a deductive system $\Xi$ (for instance, Hilbert-Ackerman proof system). Let $\phi$ be a formula and let $l=(\psi_1, \ldots, \psi_n=\phi)$ be a ...
0
votes
0answers
129 views

Counting points in elliptic curves

Given an elliptic curve over $\mathbb Z_n$ Is it $\#P$ hard to compute $\# E(\mathbb Z_n)$? Is it $PP$-hard to compute $\# E(\mathbb Z_n)\leq\frac n2$? Is it $\oplus P$ hard to compute $\# E(\...
1
vote
0answers
55 views

The chromatic polynomial of a line graph

Is there a way to obtain the chromatic polynomial of the line graph of a regular simple graph, having known the chromatic polynomial of the graph? There already exist characterizations of line graph ...
0
votes
0answers
37 views

Is there a reversible fully polynomial-time approximation scheme for polygonal billiards?

Let $P \subset \mathbb{R}^2$ be a polygon with rational coordinates, and consider discrete billiards inside $P$, where a ball (of zero radius) moves by steps of fixed length on each step, in a ...
6
votes
0answers
118 views

The provability logic of $I\Delta_0+\Omega_1 $ and complexity theory

Almost 30 years ago, a number of folks in provability logic tried to show that GL (see for instance the excellent survey by Rineke Verbrugge here) is indeed the logic of $I\Delta_0+\Omega_1$ (in the ...
0
votes
1answer
101 views

Linear programming with exponential inequalities and rational variables

If we are given a set of real linear inequalities then using elimination theory or just linear programming we can decide. If the program also has inequalities of form $2^x\leq g$ in addition to linear ...
0
votes
0answers
15 views

Complexity of finding matchings with bounds on weight-sum

Question: what is the complexity of finding a matching of maximal weight-sum below a given bound? I couldn't find anything in that respect online; maybe only because I do not know what to feed into ...
12
votes
0answers
204 views

Does the Angel have to be really smart?

My question is about the computational complexity of the Angel's strategy in the Angels and Devils game, tl;dr does the Angel have a polynomial time strategy. I'm a big Conway fan, so as you can ...
0
votes
1answer
72 views

Complexity of edge coloring of class 1 graphs

We know that the decision problem of classifying the graphs as class $1$ or class $2$ (with respect to edge coloring) is NP-complete. But, suppose we have to prove a graph to be in class $1$. Does it ...
1
vote
0answers
26 views

Modified straightline complexity of almost square of sums

Assume every linear operation (such as inner product with constant vector) can be performed in one step and multiplication by variables (quadratic operation) can be performed in one step. We know the ...
2
votes
0answers
54 views

Number of solutions to linear diophantine equations, with natural coefficients in a box

Let c, k, d $ \in \mathbb{N} $, let a, x $ \in \mathbb{N}^k $ suppose for all i $ \leq $ k, $ x_i \leq d $, $ a_i \in \mathcal{O}(d2^i) $ and $ \sum{a_ix_i} = c $ my question is for the value of c ...
0
votes
0answers
36 views

A quasi-polynomial time PTAS for a MAX SNP-hard problem implies that $NP \subseteq QP$

I'm reading a paper [Jiang, Tao; Li, Ming; On the approximation of shortest common supersequences and longest common subsequences. SIAM J. Comput. 24 (1995), no. 5, 1122–1139.] with some non-...
0
votes
0answers
45 views

Gröbner basis and integer programming

I was studying about grobner basis and observed one application of it in integer programming which is pretty much amazing but tougher than available methods like branch bound. Then what is the benefit ...
1
vote
0answers
157 views

Computational complexity of computing the trace of a matrix product under some structure

I have two problems related to computing some trace, and some (possibly suboptimal) answers. My question is about a potential more efficient algorithm for each one. (More interested in an answer to ...

1
2 3 4 5
22