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
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 ...

1
2 3 4 5
26