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,297
questions
7
votes
7
answers
3k
views
Efficient Hamiltonian cycle algorithms for graph classes
Generally speaking, finding a Hamiltonian cycle is NP-Hard and so tough. But if $G=L(H)$ is the line graph of $H$, then we can reduce the problem of finding a Hamiltonian cycle in $G$ to finding an ...
0
votes
0
answers
67
views
Quasi polynomial algorithm for NP complete problem [closed]
I know that quasi polynomial algorithm is neither polynomial nor exponential. But I want to know if we find such algorithm for NP complete problem, will it be of any use? Or is there such algorithm ...
1
vote
2
answers
246
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 ...
2
votes
0
answers
105
views
How to know if a random natural number is a probable semiprime?
Let that $n\in\Bbb N$ generated from a hash function where $n$ is long enough to be hard to factor in the gnfs algorithm. How to check if $n$ is probably a semi‑prime in a faster way than factoring it ...
0
votes
0
answers
78
views
Obstacles to computing $\pi(n)$ in $O(n^{2/3-\epsilon})$ time
Edit: Apologies, as mentioned in the comments I failed to notice the analytic algorithms that take $O(n^{1/2+\epsilon})$ time, so this question doesn’t make much sense. It’s possible there is a ...
3
votes
0
answers
235
views
Is there a version of 3-SAT that is NP-complete but grows like $2^n$ instead of $2^{n \choose 3}$?
If I have $n$ variables and I want to write down all 3-SAT problems, the number of problems is $2^{8{n \choose 3}}$, since each clause has 3 variables and each variable can be negated or not.
But ...
0
votes
0
answers
27
views
Prove the NP-hardness of the following problem: Whether there exists a partition for a set of data points
Can anybody help me prove the NP-hardness of the following question:
Given $x_0, x_1, ..., x_m \in \mathbb{R}^n$, determine whether there exists a partition $S\cup [m]\backslash S$, such that $x_0 \in ...
1
vote
0
answers
57
views
Primality testing by reversible computation using the prime number theorem
Suppose we want to build a primality testing algorithm for the numbers limited to the set $A =\{1, ..., 2^n\}$ and $n$ is reasonably large. The prime-number theorem tells us that there are ...
2
votes
0
answers
56
views
How to check that a number probably/likely has a divisor having a specific bit length/in range?
Given a randomly generated $\alpha\in\Bbb N$ where $\alpha$ is large thus hard to factor (no small prime composites). How to check that a divisor $F\in\Bbb N$ with a specific bitlengh $n\in\Bbb N∧n<...
2
votes
0
answers
70
views
Is there a sharp phase change on circuit error rate near the error correction threshold?
(I asked this question on cstheory here, but it received no attention for four days. Hopefully it is okay to move it to mathoverflow.)
My rough intuition is that if we want to efficiently compute ...
8
votes
4
answers
969
views
Does IP = PSPACE work over other rings?
Background: It is possible (see e.g., this) to define a Turing machine over an arbitrary ring. It reduces to the classical notion when the ring is $\mathbb{Z}_2$; the key difference is that ...
1
vote
0
answers
159
views
Fast algorithm for computing certain signal transformations
Let $f,g,h:\mathbb Z\to\mathbb C$ supported on $[-n,n]$. For $\tau\in \mathbb Z$, let $\operatorname{sh}_\tau f$ be the shift of $f$ by $\tau$ (i.e. $(\operatorname{sh}_\tau f)(t) = f(t-\tau)$). ...
0
votes
0
answers
73
views
Some new questions on Rademacher complexity
For $A\subset R^n$,$A=(a_1,a_2,\dots, a_n)$, $\sigma_i$ are Rademacher random variable.
Is $|\mathbb{E}_\sigma \inf_{a\in A}\sum_{i=1}^n\sigma_ia_i| \le |\mathbb{E}_\sigma \sup_{a\in A}\sum_{i=1}^n\...
3
votes
1
answer
214
views
On shortest vector problem
Assume we have an oracle which gives the length of the shortest vector in a lattice. Given this oracle can we find the shortest vector in polynomial time?
13
votes
6
answers
2k
views
Which model of computation is "the best"?
In 1937 Turing described a Turing machine. Since then many models of computation have been decribed in attempt to find a model which is like a real computer but still simple enough to design and ...
12
votes
2
answers
959
views
Drawing 3-configurations of points and lines with straight lines
It is well-known that the black-and-white coloring of the Heawood graph on 14 vertices determines a combinatorial 3-configuration with 7 "points" and 7 "lines", known as Fano plane....
4
votes
0
answers
135
views
Permutation generation problem using swaps
This is motivated by Aaronson's post, Probability of generating a desired permutation by random swaps. I am interested in a related problem where the swaps are given in the input.
We're given as input ...
0
votes
0
answers
52
views
complexity of membership problem in finite general linear group
Suppose $G$ is a subgroup of $GL(n,q)$ given by a list of generators. What is known about the complexity of the corresponding "membership problem", that is, the problem of deciding whether a ...
1
vote
0
answers
112
views
Integration in polynomial time
The work of Friedman and Ko and
Müller guarantee the polynomial time computability of the integrals of analytic functions inside the circle of convergence. But do algorithms have practical value? Is ...
6
votes
2
answers
661
views
Can knowing ahead the length of 3-SAT instance really help?
If I say I can solve 3-SAT ( known to be NP-complete) in polynomial time, yet with the following 'little' proviso:
Give me first $n$ the length of your 3-SAT formula, then give me some time on my own ,...
3
votes
1
answer
774
views
Language equivalence between deterministic and non-deterministic counter net
One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that
cannot decrease below zero and cannot be explicitly tested for zero.
An OCN $A$ over alphabet $\sum$ accepts a ...
3
votes
3
answers
5k
views
Determining the space complexity of van Emde Boas trees
We call $S(u)$ the space complexity of the vEB tree holding elements in the range $0$ to $u-1$, and suppose without loss of generality that $u$ is of the form $2^{2^k}$.
It's easy to get the ...
2
votes
0
answers
91
views
What is the complexity / name of word search problem in linear groups?
This is a question about a search problem associated with user6976's question. Suppose we are given a finite set of elements $S \subset \mathrm{GL}_n(\mathbb{Q})$ containing inverses of all its ...
8
votes
4
answers
868
views
Does there exist a general theory of "arithmetic complexity"/"arithmetic height"?
This question is hopelessly vague, but here goes:
Say I'm given some finite precision complex number, which I'm told is algebraic over $\mathbb{Q}$. Is there some well defined notion of arithmetic ...
13
votes
1
answer
375
views
Two-player independent set game
Let $G = (V, E)$ be a finite graph, and $S \subseteq V$ initially be an empty set. Alice and Bob play a game, making moves in turns starting with Alice. A move consists of choosing a vertex $v \in V \...
3
votes
0
answers
95
views
Positive boolean satisfiability problem : finding minimal solutions
Consider, over a finite set of boolean variables $X$, a Boolean system in CNF (conjunctive normal form) whose clauses only contain non-negated literals.
For every assignment of the variables which ...
6
votes
3
answers
1k
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 ...
5
votes
0
answers
74
views
Complexity and length
Suppose we define continuous piecewise linear functions $f$ on $[0,1]$ using your favorite programming language, or by finite automata, or by any other suitable machine. Define the complexity $H(f)$ ...
21
votes
3
answers
6k
views
What are the current breakthroughs of Geometric Complexity Theory?
I've read from Wikipedia about Geometric Complexity Theory (GCT) which (if I understood correctly) is a program for coping with the $ P=NP $ problem using algebraic methods.
That program seems ...
1
vote
0
answers
47
views
Computational complexity of exact computation of the doubling dimension
Given a finite metric space $X$, the doubling constant of $X$ is the smallest integer $k$ such that any ball of arbitrary radius $r$ can be covered by at most $k$ balls of radius $r/2$. The doubling ...
9
votes
3
answers
2k
views
SDP Feasibility
I have a decision problem that I have formulated as a feasibility SDP. The answer to the decision problem depends on whether the SDP is feasible or not. It is known that a SDP can be solved to ...
1
vote
0
answers
47
views
Computing geodesic length of Euclidean lines in the manifold of positive definite matrices
I am working with the manifold of positive definite matrices $PD(n)$ equipped with the affine-invariant Riemannian metric (AIRM) $g_P(V,W):=tr(P^{-1}VP^{-1}W)$, where $P \in PD(n)$ and $V,W \in T_P PD(...
0
votes
0
answers
13
views
Complexity of finding single source paths with capacity constraints and length constraints
Let $G=(V,A)$ be a directed graph with distinguished vertex $s\in V$ and let $c:A\rightarrow{\mathbb N}$ denote arc capacities. For any $t\in V,t\not=s$ we are given two numbers: $C_{t},L_{t}$. Let $...
13
votes
6
answers
4k
views
Non-constructive proofs vs. efficient algorithms
My question concerns what is meant by "nonconstructive", and whether it has ever been defined in terms of computational complexity.
The wikipedia article on constructive proof begins, "a constructive ...
0
votes
0
answers
146
views
Solve NP-hard type problems with linear programming
I would like to know if there is any way to solve an NP-hard type problem, for example, the TSP, sum of subsets or knapsack problem, by using linear programming and not by brute force.
I ask this ...
4
votes
0
answers
192
views
Computational complexity of zeros of an analytic function
The work of Friedman and Ko, page 342, Corollary 4.3.1
states that all zeros of analytic polynomial time computable function are polynomial time computable, but for me that is not clear how it could ...
3
votes
1
answer
267
views
Root finding algorithm for an analytic function
Given an analytic function $f(x)$. What is the best algorithm to find roots on the interval $[a,b]$ inside the radius of convergence> What is its complexity with respect to the length of input of ...
1
vote
0
answers
64
views
Circulant matrix inverse in $GF(p)$
For a polynomial $C(x)=c_0+\dots+c_n x^n$, consider a circulant matrix $C$ such that
$$
C= \begin{pmatrix}
c_0 & c_{n-1} & \cdots & c_2 & c_1 \\
c_1 & c_0 &...
2
votes
1
answer
207
views
Fast inverse of asymmetric diagonally dominant matrix with diagonal 1 and non-positive off-diagonals
I am interested in ways to obtain (even approximately) the inverse of an asymmetric diagonally dominant matrix with diagonal 1 and non-positive off-diagonals.
Formally, let $A$ be a $n\times n$ matrix ...
30
votes
5
answers
13k
views
Can all convex optimization problems be solved in polynomial time using interior-point algorithms?
Just a new guy in optimization. Is it true that all convex optimization problems can be solved in polynomial time using interior-point algorithms?
15
votes
0
answers
465
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 ...
2
votes
1
answer
187
views
Slicing bivariate exponential generating functions on x and y
Let $F(x, y) = e^{y D(x)}$ be a generating function for sets of objects enumerated by $D(x)$ that also keeps track of the number of sets (enumerated by the variable $y$, while $x$ enumerates the total ...
0
votes
0
answers
64
views
Counting distinct elements in smallest number of queries
There is an array of objects $a_1, \dots, a_n$. For any two objects, we can ask if they're equal or not. Our goal is to find the number of distinct objects in the array by only asking such queries. ...
1
vote
0
answers
42
views
Complexity of the TSP for hypercube graphs
Question:
what is known about the complexity of finding the Hamilton cycle of minimum weight in graphs that resemble hypercubes with weighted edges?
7
votes
1
answer
243
views
Efficiently computing $\sum_k x^{k^2}$ modulo $p$
Let $p$ be prime. There is a whole host of "large" degree polynomials that can be computed efficiently modulo $p$. I was wondering if:
$$q(x) = \sum_{k=0}^{p-1} x^{k^2}$$
is a polynomial ...
3
votes
0
answers
86
views
Efficient multiplication of Cayley-Dickson numbers
The question was already asked here, but doesn't have any meaningful answer, hence I'd like to re-post it.
Assuming that we have an algebra with conjugation, we can use Cayley-Dickson construction to ...
2
votes
1
answer
55
views
NP-hardness of vertex cover for 3-chromatic graphs
Is the vertex cover problem remains NP-hard for 3-chromatic graphs?
I am almost certain it is, but was unable to find a reference.
Thanks.
5
votes
0
answers
180
views
Complexity implications on computability
Are there any known links between complexity theory and computability theory by which I mean non-trivial theorems of the form: If NP $\neq$ co-NP then there is no strong minimal pair of r.e. sets or ...
4
votes
1
answer
244
views
Can addition and muliplication be simultaneously easy?
I just did a stint at a math festival, and had a quick conversation with a young student about how different notation systems make different operations easy. On the train home, I started wondering the ...
5
votes
0
answers
160
views
What is the fastest algorithm for multiplying one given number with many others?
When multiplying two numbers with each other, which are $n$-bit numbers, there are several algorithms like the one of Karatsuba ($O(n^{\log_2 3})$) and a new one doing it even better (Harvey - Van der ...