All Questions
1,809 questions
7
votes
0
answers
522
views
Is integer GCD in NC?
Wikipedia, in the page http://en.wikipedia.org/wiki/Greatest_common_divisor#Complexity mentions integer GCD is in NC by citing http://www.cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci07.pdf
...
- 13.9k
6
votes
6
answers
3k
views
Circumference of Convex Shapes
Here is a puzzle I found in Mitteilungen der DMV (roughly, "Letters of the German Society of Mathematicians"), issue 19/2011. It was posed by Alfred Schreiber in "Wie man Hasen fangt" (How to catch ...
6
votes
2
answers
691
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 ,...
- 1,306
6
votes
2
answers
1k
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. ...
- 9,330
6
votes
5
answers
3k
views
Where is it shown how to construct a decomposition tree for a series-parallel graph in linear time?
There are two common ways to define a series-parallel graph (or 2-terminal series-parallel graph).
Definition 1
start with K_2 marking both vertices as terminals
repeatedly join two smaller 2-...
- 12.7k
6
votes
3
answers
1k
views
computational complexity of primitive recursive functions
If we have a rewrite system for primitive recursive functions, which simplifies each term according to how the function was defined, then what is the computational complexity of this calculation? That ...
- 63
6
votes
3
answers
961
views
What new primitive recursive functions are needed to reconcile Turing time complexity with Gödel time complexity?
Let me begin with an example.
Consider the computable function $f(x) = 2x$. A Turing machine can implement this function in $O(|n|)$ steps: simply walk to the end of the input string, write a $0$, ...
- 693
6
votes
2
answers
2k
views
An Alternative to the Cook-Levin Theorem
In general to prove that a given problem is NP-complete we show that a known NP-complete problem is reducible to it. This process is possible since Cook and Levin used the logical structure of NP to ...
- 115
6
votes
2
answers
2k
views
Variation on the Subset Sum Problem
Given a nonempty set of integers, and given that there exists a subset of this set whose elements sum to zero, is finding the smallest such subset NP-complete?
Disclaimer: The above question ...
- 259
6
votes
1
answer
2k
views
Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?
Not sure whether this question belongs here or math.stackexchange.
You can assume that all the vertices are unique. The given vertices can be the vertices of the polygon, thus they do NOT have to be ...
- 163
6
votes
2
answers
1k
views
Linear programming is continuous
Consider an arbitrary linear program:
$$\max \vec c \cdot \vec x$$
subject to:
$$\textbf{A}\cdot \vec x = 0, \quad \vec a \le \vec x \le \vec b$$
Assume that this program is feasible and bounded. ...
- 884
6
votes
4
answers
909
views
How long does it take to compute a class number?
I was wondering if there are any known (upper and lower) bounds for the complexity of computing the class-number of a finite extension of the rationals. (A general bound should be in function of the ...
- 3,399
6
votes
2
answers
256
views
Form a $\mathbb{Z}^d$ lattice cycle from given lengths
Suppose you are given a list of integer lengths,
e.g.,
$(5,3,2,2,1,1,2,1,1)$.
The task is to decide if they can form a closed cycle
in $\mathbb{Z}^d$ by connecting segments of those
lengths in order, ...
- 151k
6
votes
2
answers
908
views
A Query regarding the Halting Problem (Omega): Halting Probability for Given Input Size
I was studying the Halting Problem in context of the Probability and had a few doubts regarding it. Hope someone could help me out.
I am aware of the probability of a Random program halting on a ...
- 81
6
votes
2
answers
564
views
Funky congruences
Suppose we have the remainders: {$(a^0_1, a^1_1), \ldots, (a^0_n, a^1_n)$} and the moduli {$c_1, \ldots, c_n$}. We want to know if there exists $b_1, \ldots, b_n \in$ {0,1} and $m \in \mathbb{N}$ such ...
- 265
6
votes
2
answers
2k
views
Complexity of rectangular matrix multiplication
I am interested in the complexity of multiplying two matrices $A$ and $B$, i.e. to compute $AB$.
From [Le Gall and Urrotia], I know that:
if $A$ and $B$ are square-matrices of size $n$, then this can ...
- 562
6
votes
2
answers
376
views
Functions that can be computed faster simultaneously than expected
The following is an elementary question about circuit complexity. It is different from the kind of thing I have seen discussed, so I would be interested in any work that has been done on this kind of ...
- 95
6
votes
1
answer
1k
views
Finding a cycle of fixed length in a bipartite graph
Is finding a cycle of fixed even length in a bipartite graph any easier than finding a cycle of fixed even length in a general graph? This question is related to the question on Finding a cycle of ...
- 784
6
votes
2
answers
276
views
Extending polynomial hierarchy above $\omega$
The arithmetic hierarchy is naturally extended to all ordinals via ordinal notations creating a hierarchy for all hyperarithmetic sets. The polynomial time hierarchy is defined analogously to the ...
- 3,029
6
votes
2
answers
1k
views
Approximate number of primes below a given integer?
The problem of the complexity of the exact counting problem for primes is interesting. The best result we have about primes is that it is hard for TC0. But counting the number of witnesses to a TC0 ...
- 61
6
votes
2
answers
518
views
A minimum set hitting every base of a matroid
We are given a matroid. Our goal is to find a set of elements of minimum size that has non-empty intersection with every base of the matroid. Is the problem studied before? Is it in P? For example, in ...
- 115
6
votes
1
answer
761
views
Checking if one polytope is contained in another
I have two sets of inequalities, say, $Ax \leq 0$ and $Bx \leq 0$. I would like to know if they both define the same polytope. Or, even, whether one is contained in the other.
At the moment I am ...
- 491
6
votes
1
answer
357
views
computing abelianizations
Suppose I have a finitely presented group $G,$ and a subgroup $H$ of $G$ given by its finite generating set (given as words in the generators of $G.$ I want to know whether $H/[H, H]$ is finite. Is ...
- 96.4k
6
votes
2
answers
8k
views
Existence/Uniqueness of Nonnegative Solutions of Linear Systems of Equations
Suppose we have an $m$x$n$ matrix $A$, with $m\lt n$, and an $m$x$1$ vector $b$. Are there existence and uniqueness conditions characterizing nonnegative solutions of the system of linear equations $...
6
votes
3
answers
632
views
Zero-knowledge proof for $P \ne NP$?
In computational complexity, $P \ne NP$ is a widely believed conjecture. Suppose that someone discovered a proof for it. He wants to publish a proof that he correctly proved the conjecture. I am aware ...
- 2,993
6
votes
2
answers
740
views
Flat metrics on $n$-toruses, their systoles, and the "shortest vector problem"
Apologies if this is too basic, but I haven't been able to find any info about the question. Is there anything known about the moduli space of flat metrics on an $n$-torus (i.e., $(S^1)^n$)? ...
- 595
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 ...
- 972
6
votes
2
answers
400
views
Geometric dominating set: NP-complete?
Let $G=(V,E)$ be a geometric graph, a graph embedded in the plane whose edge lengths are
the Euclidean distance between its endpoint vertices.
Say that a set of vertices $D \subseteq V$ is a geometric ...
- 151k
6
votes
2
answers
1k
views
Computational complexity of Knot polynomials
What's known about computational complexity of different types of knot invariant polynomials?
For example, Evaluating Jones Polynomial is known to be #P hard.
Is there any reference that surveys such ...
- 615
6
votes
3
answers
2k
views
A simple infinite dimensional optimization problem
I'd be grateful for a reference for the following result, which I believe to be true, and
should be well-known.
Let the continuous functions $f_0,f_1,\cdots,f_n: [0,1]\rightarrow [0,\infty)$ be ...
- 520
6
votes
2
answers
308
views
Recent trends in effective analysis
The references listed at http://en.wikipedia.org/wiki/Computable_analysis have all been published 30-15 years ago. Are the approaches which these references expose still up-to-date and relevant to the ...
user60665
6
votes
1
answer
513
views
The Universality Theorem by Mnev for uniform oriented matroids of rank 4 and higher
According to the Universality Theorem by Mnev (see below theorem 8.6.6 from [1]), for any open semialgebraic variety V there is a uniform oriented matroid of rank 3 whose realization space is stably ...
- 245
6
votes
1
answer
507
views
Complexity of computing expansion of a newform level 18 weight 3 and character [3] - OEIS A116418
I am not familiar with newforms, so this may not make any sense.
OEIS sequence A116418 is Expansion of a newform level 18 weight 3 and character [3]
Numerical evidence suggest that up to $10^5$
$$ \...
- 25.4k
6
votes
2
answers
2k
views
P vs NP and OWFS
It is known (simple HW exercise) that:
If P = NP, that OWFs (one way functions) can not exist.
It is also known that there is a Universal OWF:
namely, there is a function f:
s.t. if any OWF ...
6
votes
4
answers
2k
views
Examples of Super-polynomial time algorithmic/induction proofs?
In combinatorics, one can sometimes get an algorithmic proof, which loosely has the following form:
-The proof moves through stages
-An invariant is shown to hold by induction from previous stages
-...
- 1,088
6
votes
1
answer
1k
views
MIP^*=RE and quantum computation
I recently learned about the MIP^*=RE result. I have to admit that I don't understand big parts of this paper and I am barely familiar with quantum physics. I hope my questions below make sense.
I ...
- 2,882
6
votes
1
answer
609
views
Attempt at applying linear programming to the partial sums of the Möbius inverse of the Harmonic numbers
Let $a(n)$ be the Dirichlet inverse of the Euler totient function:
$$a(n) = \sum\limits_{d|n} d \cdot \mu(d) \tag{1}$$
and let the matrix $T(n,k)$ be:
$$T(n,k)=a(\gcd(n,k)) \tag{2}$$
It has been ...
- 1,183
6
votes
1
answer
861
views
Is Binary Integer Linear Programming solvable in polynomial time?
The paper Solving the Binary Linear Programming Model in Polynomial Time claims that Binary Integer Linear Programming is in P. However, it seems that no subsequent literature in the mainstream has ...
- 221
6
votes
2
answers
426
views
Complexity of detecting a convex body in $\mathbb{R}^n$?
Let $K_0$ be a bounded convex set in $\mathbb{R}^n$ within which lie two sets $K_1$ and $K_2$. $K_0,K_1,K_2$ have nonempty interior. Assume that,
$K_1\cup K_2=K_0$ and $K_1\cap K_2=\emptyset$.
The ...
- 111
6
votes
3
answers
11k
views
Maximum flow with negative capacities?
I'm trying to compute an (s-t) maximum flow through a network which includes a number of arc pairs ((u,v), (v,u)) that have equal, negative capacities (weights). I'm not aware of any efficient ...
- 83
6
votes
1
answer
376
views
How does the complexity of calculating the Permanent imply the NP completeness of directed 3-cycle cover?
In their paper Two Approximation Algorithms for 3-Cycle Covers of Markus Bläser and Bodo Manthey it is stated that:
"...deciding whether an unweighted directed graph has a 3-cycle cover is ...
- 13.2k
6
votes
1
answer
779
views
If $\ell_0$ regularization can be done via the proximal operator, why are people still using LASSO?
I have just learned that a general framework in constrained optimization is called "proximal gradient optimization". It is interesting that the $\ell_0$ "norm" is also associated with a proximal ...
6
votes
1
answer
216
views
A "dense" extension of the set of primitive recursive functions
Let $\mathcal{PR}$ be the set of primitive recursive functions. Let $\mathcal{PR}(f)$ be $\mathcal{PR}$ which we have amplified by adding (a recursive) $f$ the in the set of initial functions. To make ...
user39297
6
votes
1
answer
1k
views
Exact arithmetic for real algebraic numbers
There was a reply to a question (that I can't find) which mentioned SARAG (Some Algorithms
in Real Algebraic Geometry) see http://perso.univ-rennes1.fr/marie-francoise.roy/bpr-ed2-posted2.html. This ...
- 9,132
6
votes
1
answer
549
views
non-deterministic turing machines
I have one simple question:
There is a set, which can be decided in polynomial time by a (one-band) non-deterministic Turing Machine.
Why should there exist one (one-band) non-deterministic Turing ...
- 185
6
votes
1
answer
384
views
Collapsing of exptime and alternation bounded turing machine
Hello
Let C be a set of function (let say time-computable increasing function to avoid pathological cases).
Let's call $\rm{ATIME}(C,j)$ the class of langages decided by a Turing Machine begining in ...
6
votes
1
answer
336
views
Is this problem of selecting points NP-hard?
I have an optimization problem related, in a certain way, to the expression of a set of points with the least number of points and I don't know if it is NP-hard (or not).
More formally, I have a ...
- 63
6
votes
1
answer
3k
views
Does MCMC overcome the curse of dimensionality?
I want to compute an integral like this
$$\frac{\int_y g(y) e^{-\beta f(y)} \text{d} y } {\int_y e^{-\beta f(y)} \text{d} y}$$
where $f(y)$ is not necessarily convex and the dimension $d$ of $y$ is ...
- 73
6
votes
1
answer
1k
views
The relationship between P vs NP problem and "Kolmogorov complexity with time"
Let $P$ - polynomial($P(x) \ge x$), $n \in \mathbb{N}$, $l < log(n)$.
Problem1: "Is there program with length $\le l$ that print $n$ by using $\le P(log(n))$ time?"
Is it Problem1 $\in NP$-...
- 2,576
6
votes
1
answer
3k
views
Stochastic Matrix: Second largest eigenvalue and second largest absolute value of eigen value
Setup
Let $A$ be a stochastic matrix.
Let the eigenvalues of $A$ be $1 = \lambda_1 \geq \lambda_2 \geq \lambda_3 ... \geq -1$.
Let $\lambda = \max_{x: x \perp 1} \frac{||Ax||}{|| x ||}$
Question:
...
