All Questions
598 questions with no upvoted or accepted answers
7
votes
0
answers
252
views
When is a reduction not a reduction?
Every mathematician understands the concept of reducing a complicated problem to a simpler problem. "Without loss of generality, we may assume…" However, I've noticed that some kinds of "...
- 82.6k
7
votes
0
answers
298
views
Feasible Type Theories
I am looking for references about efficient type theories,
efficiency in the sense of computational complexity,
and type theory in the sense of Martin-Lof's type theories.
Has there been any studies ...
- 5,502
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
0
answers
151
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 ...
- 1,171
6
votes
0
answers
65
views
Vertex cover in bipartite graphs with bounds on cost and size
Suppose we have a bipartite graph $G$ with non-negative integer vertex costs. We would like to find a vertex cover of cost at most $C$ and size (number of vertices) at most $S$, where $C$ and $S$ are ...
- 96
6
votes
0
answers
105
views
Computing the zeta transform of a Boolean function: Space-time tradeoff
Let $f : \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function in $n$ variables. The zeta transform of $f$ is the Boolean function $\zeta_f : \mathbb{F}_2^n \to \mathbb{F}_2$ defined by
$$\zeta_f(y) :...
- 71
6
votes
0
answers
96
views
Finding the maximal component of a vector in sublinear time
Given a vector $u \in \Bbb R^n$, finding the value of the largest component of $u$ needs linear time in $n$. However, what if we additionally know that $u$ lies in some linear subspace $U \subset \Bbb ...
- 13.6k
6
votes
0
answers
116
views
On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?
Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate $P=BPP$ in $1986$. They do this without getting into circuit lower bounds and from a different view ...
- 13.9k
6
votes
0
answers
237
views
Complexity of scissors congruence?
Where is the complexity of the problem 'Given two bounded compact convex integral polyhedra in $\mathbb R^n$ presented by $O(poly(n))$ integer valued halfspaces given by linear inequalities with ...
- 13.9k
6
votes
0
answers
232
views
Is there a "promise" at the heart of mixing times for random walks on Cayley-graphs?
I'm interested in some questions about the computational complexity of bounding the mixing time of random walks on Cayley-graphs of finite groups like that of the Rubik's Cube Group $G$. Determining ...
- 2,185
6
votes
0
answers
208
views
Is there a decomposition strengthening of the Sauer-Shelah Lemma?
Let $S \subset \{-1,1\}^n$. For a subset $A \subset [n]$ let $P_A$ denote the coordinate projection operator on S; in other words let $P_A(S)$ be the coordinate projection of $S$ onto the coordinates ...
- 13k
6
votes
0
answers
69
views
Digraph weak connectivity in $O(V)$ space and $O(V+E)$ time
A digraph is called weakly connected if its underlying undirected graph is connected.
You are given a digraph $G$ with $V$ vertices and $E$ edges as a read-only data structure consisting of lists of ...
- 37.7k
6
votes
0
answers
97
views
Finding the optimal mixture of two convex functions
I am trying to find an efficient way to solve the problem $$\min_{p,x_1,x_2} p\cdot f(x_1)+ (1-p) \cdot f(x_2)~~~~~ s.t.\\p\cdot g_1(x_1) + (1-p)\cdot g_2(x_2)\leq 1 \\ 0\leq p \leq 1$$ where $x_1,x_2\...
6
votes
0
answers
154
views
Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph
According to a conjecture:
Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common.
Equivalent statement here
Main question:
...
- 25.4k
6
votes
0
answers
317
views
Variant of orthogonal Procrustes problem
The orthogonal Procrustes problem seeks a matrix $M$ that minimizes $||AM-B||_F$ subject to $M^TM=I$, where $M$ is $d\times d$ and both $A$ and $B$ are $n\times d$. Geometrically, $M$ rotates a set of ...
- 61
6
votes
0
answers
346
views
Enumerating (generalized) de Bruijn tori
Given a cyclic word $w$ of length $N$ over a $q$-ary alphabet and $k \in \mathbb{Z}_+$, consider the directed multigraph $G_k(w) = (V,E)$ with $V \subset$ {$1,\dots,q$}$^k$ given by the $k$-lets (i.e.,...
- 15.4k
6
votes
1
answer
368
views
Time functions of non-deterministic Turing machines
Let $M$ be a non-deterministic Turing machine which recognizes a language $L$, that is, for every input word $u$ there is an accepting computation with input $u$ if and only if $u\in L$. The smallest ...
user6976
5
votes
0
answers
75
views
What is the maximal advantage of randomized over deterministic algorithms for approximation in the worst-case?
Let $X\subset Y$ be Banach spaces and $B_X:=\{x\in X: \|x\|_X\le1\}$ be the unit ball of $X$.
The goal is to find an approximation of every element from $B_X$ with error measured in $Y$ by using at ...
5
votes
0
answers
199
views
In finite model theory, is "invariant FOL with $\varepsilon$-operator" unavoidably second-order?
Throughout, all structures are finite.
Say that a class of finite structures $\mathbb{K}$ is $\mathsf{FOL}_\varepsilon^\text{inv}$-elementary iff it is the class of finite models of a sentence in the ...
- 21.2k
5
votes
0
answers
192
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 ...
- 3,029
5
votes
0
answers
184
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 ...
- 749
5
votes
0
answers
180
views
Is the matrix multiplication exponent $\omega$ independent from the choice of the base field
The matrix multiplication exponent, usually denoted by $\omega_{F}$, is the smallest real number for which any two $n\times n$ matrices over a field $F$ can be multiplied together using ${\...
- 151
5
votes
0
answers
129
views
Finding an $\mathbb{F}_q$-point on one specific intersection of quadrics
Let $\mathbb{F}_q$ be a finite field of large characteristic and $a_1, a_2, \cdots, a_n \in \mathbb{F}_q$ be some pairwise different elements. I assume that $\sqrt{-1} \in \mathbb{F}_q$. Consider the ...
- 1,833
5
votes
0
answers
292
views
Fastest sine of a large power of 2
What is the fastest known way to calculate $\sin(2^{n})$ for large integer $n$?
I only need the highest few bits to be correct. I suspect that the compute time required
scales with $n$ (and actually ...
- 1,547
5
votes
0
answers
179
views
Certificate for computation of ideal class group
Is there a known way of producing a certificate that can be used to more quickly verify that an ideal class group of a number field was computed correctly? More formally, I would like to know if there'...
- 1,856
5
votes
0
answers
240
views
Existence of $\{0,1\}$-solution to a system of linear equations with coefficients in $\{0,1\}$
Crossposted at Theoretical Computer Science SE
A problem I study reduces to a system of linear equations $A\mathbf{x}=\mathbf{1}$ where $A$ is an $m\times n$ matrix with each entry $a_{ij}\in\{0,1\}$....
- 123
5
votes
0
answers
267
views
Are there any neusis-hard/neusis-complete problems?
I have lately been enjoying Richeson's Tales of Impossibility (see MAA review), an accessible book on the famous problems of Euclidean geometry including angle trisection/cube doubling/heptagon ...
- 2,185
5
votes
0
answers
246
views
Does $\mathsf{Q}$ have any interesting provably recursive functions?
This question was asked and bountied at MSE without success.
For an appropriate theory $T$, say that an $n$-ary $T$-provably recursive function is a $\Sigma_1$ formula $\varphi$ with $n+1$ free ...
- 21.2k
5
votes
0
answers
85
views
special classes of ideals (eg. toric) that admit faster Buchberger algorithm?
I have heard that toric ideals allow one to speed up the Buchberger algorithm considerably (see Grobner bases of toric ideals, Remark 2,3). My question is two-fold:
What are the precise complexity-...
- 1,221
5
votes
0
answers
301
views
The expressiveness of functions computable on trees
Motivation:
Let's define a function computable on a $k$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary ...
- 3,871
5
votes
0
answers
125
views
Is integer circuit membership undecidable?
According to wikipedia
integer circuit
in its simplest form is succinct representation of multivariate polynomial with
integer coefficients. Decidability if an integer is represented by the integer ...
- 25.4k
5
votes
0
answers
87
views
Problem to efficiently compute the Volume of $d$ anchored 4D cuboids
An easy still unsolved special case of Klee's measure problem with applications in multiple objective optimization is described in the following.
Let $[\vec a_1,\vec b_1],\dots,[\vec a_n,\vec b_n]$ ...
- 4,535
5
votes
0
answers
78
views
Complexity of calculating $f^{(n)}(0)$/extracting a coefficient of a functions taylor-series
Many combinatorial problems can be solved using generating functions.
In such a case, we obtain a function $f(x)$, which (for usual) has a taylor-expansion:
$$
f(x) = \sum_{n\ge 0 } a_n x^n
$$
So ...
- 151
5
votes
0
answers
265
views
Finite axiomatizability and $\mathrm{PA^{top}}$
Is $\mathrm{PA^{top}}$ finitely axiomatizable? If not, does it have a finitely axiomatizable extension (allowing new predicates but not new variable types) that has arbitrarily large finite models?
$\...
- 7,545
5
votes
0
answers
162
views
Homogeneous linear and quadratic inequalities
I have a bunch of vectors $b_i \in R^n$ for $i = 1,\ldots,N$ and a bunch of (indefinite) matrices $A_j$ for $j = 1,\ldots,M$. Let's consider the set $S \subset R^n$ of $x \in R^n$ vectors such that
$$...
- 1,150
5
votes
0
answers
137
views
How many CNOT gates are needed to compute scalar multiplication in a finite field of characteristic 2?
I want to know if scalar multiplication over a finite field of characteristic 2 is generally easier to compute than a linear transformation over a vector space over $F_{2}$.
Suppose that $p(x)$ is an ...
5
votes
0
answers
106
views
Collapsing the Exponential time Hierarchy with a complete language as oracle
It is known that $\mathsf{P^A=NP^A}$ is true for every $\mathsf{EXP}$ complete language $\mathsf{A}$. The question is the whether the similar things hold for Exponential time Hierarchy.
Is there ...
- 1,689
5
votes
0
answers
307
views
Quantum P vs NP equivalent problem
If $P = NP$, does it follow that $BQP = NP^{BQP}$?
I came up with this question when I was thinking about how $P = NP$ can be described as "does every decision problem where a proof for YES can be ...
- 51
5
votes
0
answers
84
views
One-sided version of the random oracle hypothesis
The random oracle hypothesis states that relationships between complexity classes hold iff they hold relativized to a random oracle with probability 1. This is false, but all of the counterexamples I ...
- 2,130
5
votes
0
answers
126
views
Collapsing the Intuitionistic Bounded Arithmetics Hierarchy
Let $iT$ be the intuitionistic first order theory with non-logical axioms of classical first order theory $T$.
Theorem1. If $\mathsf{T^i_2}\vdash \mathsf{T_2}$, then $\mathsf{T^i_2}$ proves that the ...
- 1,689
5
votes
0
answers
166
views
Fourier basis for sub-Gaussian spaces?
Let $(\mathcal{X}, \pi)$ be a probability space such that $\pi$ has full support. Consider $L^2(\mathcal{X},\pi)$ to be the inner product space of function $f: \mathcal{X}^n \to \mathbb{R}$, with ...
- 519
5
votes
0
answers
145
views
Complexity of $\mathbb{Z}^n$ tilings
Let $\mathcal{T} \subset \mathbb{Z}^n$ be a finite set. Let $\Lambda \subset \mathbb{Z}^n$ be a full rank lattice.
We say that $\mathcal{T}$ is a $\Lambda$-tile for $\mathbb{Z}^n$ if the following ...
- 800
5
votes
0
answers
222
views
Littlewood-Richardson rule for the complete flag variety: GapP complete?
The cohomology ring of a complete flag variety $X$ has a basis of Schubert classes $S_u$ for permutations $u$. Define the Littlewood-Richardson coefficient $c_{uv}^w$ for permutations $u,v,w$ to be ...
- 2,168
5
votes
0
answers
240
views
Complexity of approximating the size of the range of a matrix
Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define:
$$S_M = |\{Mx : x \in \{-1,1\}^n\}.$$
It is NP-hard to compute $S_M$ exactly I believe by applying the ...
- 3,377
5
votes
0
answers
263
views
Is there a program for theory of incompleteness in NP?
Motivated by Suresh's post, Techniques for showing that problem is in hardness limbo, it seems that there might be an underlying theory that explains why some of these problems can not be complete for ...
- 2,993
5
votes
0
answers
167
views
A specific case of the $p$-center problem
Given a fixed positive integer $m$, let $\cal{S}$ be the subset from $\mathbb{R}^m$ defined as $\cal{S} = \{u \in \mathbb{R}^m \mid \forall i \in \{1, \dots, m\}, u(i) > 0$ and $\sum_{i=1}^m{u(i) = ...
- 125
5
votes
0
answers
617
views
Any reason to believe that $NP \neq P$ is unprovable in ZFC
We know $NP \neq P$ from a lot of point of view like empirical reason,or theoretical reasons such as finite model theory or descriptive complexity.Although we find so many reasons to believe $NP \neq ...
- 3,084
5
votes
0
answers
194
views
A linear optimization problem on a graph
Let $G=(V,E)$ be a finite graph and let $f$ be any positive function defined on the vertices. Put weights on the vertices $v_{i}$, way $w_{i}$ so that $\sum_{i=1}^{n}w_{i}\leq 1$. Assume that every ...
- 2,288
5
votes
0
answers
139
views
Are there sampNP-intermediate problems?
This questions is approximately cross-posted from theoretical computer science stackexchange
Ladner's theorem establishes that if $\mathsf{P} \ne \mathsf{NP}$ then $\mathsf{NPI} := \mathsf{NP} \...
- 1,368
5
votes
0
answers
182
views
Best lower bound for proof complexity of graph asymmetry
Graph automorphism problem ( GA) of determining whether a graph has a nontrivial automorphism is a good candidate for a problem in $NP$-intermediate. I'm looking for references that study the ...
- 2,993