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
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 ...
user's user avatar
  • 19
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 ...
Geoffrey Irving's user avatar
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 ...
Robeto Leo's user avatar
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 ...
Logan 's user avatar
  • 31
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 ...
user1747134's user avatar
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<...
user2284570's user avatar
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 ...
user2284570's user avatar
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 ...
Geoffrey Irving's user avatar
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\...
Hao Yu's user avatar
  • 185
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?
Turbo's user avatar
  • 13.7k
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 ...
Mohammad Al-Turkistany's user avatar
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 ...
Pierre's user avatar
  • 2,145
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 ...
poeaqnwgo's user avatar
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 ...
Fiktor's user avatar
  • 1,264
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 ...
Christopher-Lloyd Simon's user avatar
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)$). ...
Rami's user avatar
  • 2,571
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)$ ...
Dmitrii Korshunov's user avatar
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 ...
pyridoxal_trigeminus's user avatar
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(...
Spencer Kraisler's user avatar
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 $...
Yossi Peretz's user avatar
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 ...
Juan Carlos's user avatar
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 ...
poeaqnwgo's user avatar
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 ...
poeaqnwgo's user avatar
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 &...
Oleksandr  Kulkov's user avatar
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. ...
Oleksandr  Kulkov's user avatar
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 ...
Oleksandr  Kulkov's user avatar
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?
Manfred Weis's user avatar
  • 12.6k
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 ...
Oleksandr  Kulkov's user avatar
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.
Yevgeny Levanzov's user avatar
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 ...
Peter Gerdes's user avatar
  • 2,551
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 ...
Noah Schweber's user avatar
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 ...
tobias's user avatar
  • 739
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 ...
mtheorylord's user avatar
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 ...
Tippisum's user avatar
  • 153
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''...
truebaran's user avatar
  • 9,140
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 ...
Hexirp's user avatar
  • 335
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 ...
Hao Yu's user avatar
  • 771
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. ...
truebaran's user avatar
  • 9,140
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 ...
Ro. Cohof's user avatar
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 ...
Guozhen Shen's user avatar
  • 1,288
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}~(\...
qmww987's user avatar
  • 49
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)>...
truebaran's user avatar
  • 9,140
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 ...
Honglian's user avatar
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 ...
roignoirewg's user avatar
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, ...
Makogan's user avatar
  • 123
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 ...
seed's user avatar
  • 111
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: ...
Mohammad Golshani's user avatar
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 ...
pyridoxal_trigeminus's user avatar
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 ...
Oleksandr  Kulkov's user avatar
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 ...
XL _At_Here_There's user avatar

1
2 3 4 5
26