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
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 ...
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 ...
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 ...
3
votes
0
answers
234
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 ...
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
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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)$). ...
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)$ ...
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 ...
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 $...
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 ...
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 ...
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 ...
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 &...
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. ...
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 ...
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?
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 ...
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 ...
2
votes
0
answers
60
views
Degeneracy and the "Linear Degeneracy Testing" problem
The Affine Degeneracy problem is about deciding whether $n$ given points in $\mathbb{R}^d$ (or $\mathbb{Q}^d$) are "in general position". i.e. there is no $d+1$ tuple of points which lies in ...
1
vote
0
answers
111
views
Sudden drop in complexity class due to the more general correlations
Recently I was asking about the impact of the groundbreaking result MIP*=RE on logic and proof theory (see this discussion). Surprising as it is I got confused with the following: MIP* is a ,,quantum''...
1
vote
1
answer
85
views
How large can a subset of computable reals, whose comparison function is computable, grow?
How large can a subset of computable reals, whose comparison function is computable, grow?
For example, rational numbers are computable reals, and its comparison function is computable. As another ...
0
votes
0
answers
26
views
Convergence bound for zero-order optimization method
I would like to understand the error bound for a particular zero-order optimization method: (stochastic) difference method.
To solve an nonsmooth optimization problem $min_x G(x)$ where $G$ is only a ...
5
votes
2
answers
652
views
MIP*=RE theorem and its impact on logic and proof theory
In the monumental paper MIP*=RE five authors, Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen, managed to show that two complexity classes: RE and MIP* do in fact coincide. ...
1
vote
0
answers
47
views
Hardness of an optimization problem when some variables are fixed
Given a general optimization problem, I would like to know what we can say about the hardness of the problem when a subset of its variables are fixed.
With the two (related) examples, it is clear that ...
1
vote
0
answers
56
views
Are the lower elementary functions closed under limited recursion?
The lower elementary functions (also called Skolem elementary functions) are functions generated from the successor, modified subtraction, projection functions by the operations of composition and ...
1
vote
0
answers
135
views
Complexity of calculating the expectation of $\operatorname{Tr} h(A)$, $A$ is a random matrix
$A$ is a $d_1\times d_1$ random matrix. Given $\{g_i\}~(1\leq i\leq n)$ iid Gaussian variables, $f_{ij}(g_1,g_2,...,g_n)~(1\leq i,j\leq d_1)$ are degree-$d_2$ polynomials. And $f_{ij}\equiv f_{ji}~(\...
14
votes
1
answer
1k
views
(Very) Large numbers, Chaitin's incompletness theorem and a specific upper bound
Chaitin's incompleteness theorem roughly saying states that for any theory $S$ there exists universal constant $L$ that for any string $\sigma$ one cannot prove (within this theory) that $K(\sigma)>...
2
votes
1
answer
141
views
Optimization over permutation
The Problem
This is the problem I am working on: Given a set $X = \{x_1, x_2, \cdots , x_n\}$ in a metric space, find an optimal ordering $\pi : X \rightarrow X$ that maximizes the following objective ...
1
vote
0
answers
104
views
Computing sine of gamma function [closed]
In the sense of bit complexity, how difficult is it to compute $$\sin(a\Gamma(x))$$ where $a$ is a constant and $x>1$? Is it possible to avoid the computation of $\Gamma$ as first step?
Is there a ...
2
votes
1
answer
114
views
Is the problem of vertex enumeration from an H-representation of a polytope NP-hard?
According to the Wikipedia page on the issue, the vertex enumeration problem is NP-hard.
However, double description and reverse linear search are algorithms listed to solve the problem. Moreover, ...
1
vote
0
answers
27
views
Are there any known lower complexity bounds on solving positive semidefinite or positive semidefinite feasibility problems?
I've been trying to attack the problem posted here, about quickly checking if a matrix has any positive semidefinite completions. I suspect that the answer to the question is "no", because ...
0
votes
0
answers
56
views
On diagonalizations over complexity classes
I am looking for the following PhD thesis, but could not find it, and all my attempts for finding it failed.
I am wondering if there is a way to get it:
On diagonalizations over complexity classes
By: ...
2
votes
1
answer
44
views
Complexity for determining whether a given metric space is hyperconvex?
Suppose I am given a finite metric space as a distance matrix. What is the complexity of determining whether this metric space is hyperconvex?
Definition: A metric space is said to be hyperconvex if ...
6
votes
0
answers
100
views
Complexity of continued fraction arithmetic operations
Let $A = [a_0; a_1, \dots]$ and $B = [b_0; b_1, \dots]$ be continued fractions.
Let's say that we want to compute $A+B$ or $A \cdot B$ while staying in the continued fraction representation. So, for ...
2
votes
1
answer
117
views
The counterpart of productive set with polynomial computational complexity
For definition of productive set, see here and here, that is defined with computability, or computable function. Restricting computable function as function of polynomial computational complexity, is ...