All Questions
1,809 questions
5
votes
1
answer
2k
views
Non-uniform complexity of the halting problem
This question is approximately cross-posted from Theoretical Computer Science Stack Exchange: https://cstheory.stackexchange.com/questions/14445/complexity-of-the-halting-problem
What can be said ...
5
votes
2
answers
457
views
Heaviest Convex Polygon
Suppose we have an arbitrary function $f : \mathbb{R}^2 \to \mathbb{R}$. For any subset $s \subseteq \mathbb{R}^2$, we can define $g_f(s)$ as the integral* of $f$ over the region $s$. Suppose ...
5
votes
1
answer
465
views
Computational complexity of proof verification
Let $\mathcal{L}$ be a recursive first-order theory, with a deductive system $\Xi$ (for instance, Hilbert-Ackerman proof system). Let $\phi$ be a formula and let $l=(\psi_1, \ldots, \psi_n=\phi)$ be a ...
5
votes
1
answer
502
views
Time Complexity of the Word Problem for Finite Permutation Groups
Given a finite permutation group, i.e. a subgroup of the symmetric group on $n$ symbols in terms of generators, what is the complexity of the word problem? That is, computing if two words in the ...
5
votes
2
answers
4k
views
sparsity of QR decomposition
Hi, everyone!
I have a sparse $n \times n$ matrix $A$ with $nnz(A)$ denoting the number of non-zero entries in $A$. Now I use QR factorization to decompose $A$ into an orthogonal matrix $Q$ and ...
5
votes
1
answer
2k
views
BPP being equal to #P under Oracle
Luca Trevisan here gives a randomized polynomial-time approximation algorithm for #3-coloring given an NP oracle.
In a similar vein, I was wondering if there were any results on $BPP^{NP}\stackrel{?}{...
5
votes
2
answers
3k
views
symmetric difference of languages - both are in NP and coNP
I have this problem,
Let $L_1,L_2$ be languages in $NP \cap co-NP$. I want to show that their symmetric difference is also in $NP \cap co-NP$. Like:
$L_1 \oplus L_2$ = {x | x is in exactly one of $...
5
votes
2
answers
2k
views
Multiplicative gradient descent?
The normal gradient descent is additive: $w_{t+1}=w_t-\lambda_t\nabla f(w_t)$, but is there a multiplicative gradient descent that looks something like $w_{t+1}=w_t[-\lambda_t\nabla f(w_t)]$?
I know ...
5
votes
2
answers
3k
views
Continuous Linear Programming: Estimating a Solution
I have a "continuous" linear programming problem that involves maximizing a linear function over a curved convex space. In typical LP problems, the convex space is a polytope, but in this case the ...
5
votes
1
answer
461
views
Discrete log problem modified
Suppose one is given an odd prime $p$, a generator $g$ of $(\mathbb Z/p \mathbb Z)^*$ and two integers $a$ and $b$. Is there an efficient method to determine whether $\log_g a < \log_g b$? (Here we ...
5
votes
3
answers
1k
views
Is There An Algorithmic Complexity Of A Random Distribution
Has anyone studied an equivalent to algorithmic complexity for probability distributions?
This would be a measure which was similar to Kolmogorov complexity but look at the complexity of a (discreet ...
5
votes
3
answers
1k
views
Algorithm for the intersection of a vector subspace with a cone of non-negative vectors
Hi,
I would like to know whether there is some more effective way of how to compute an intersection of a vector subspace of $\mathbb{R}^{n}$ with a cone of vectors with non-negative entries than the ...
5
votes
3
answers
8k
views
Linear programming - uniqueness of optimal solution
Is it possible to build such an objective function for a given set of constraints, so that there will be only one optimal solution?
My general problem is to get any vertex of a polytope formed by a ...
5
votes
2
answers
413
views
An interesting variant on the maximum independent set problem.
Suppose i have a graph $G=(V,E)$ with $|V|=n$. Furthermore suppose i give you a maximum independent set $\mathcal{I}$ in $G$. Now suppose i obtain a new graph $G'$ from $G$ by removing a single vertex ...
5
votes
1
answer
226
views
Complexity of counting MAXCUT in planar graphs -- seemingly contradicting claims
Confusion is likely. Appears to me two papers give contradicting claims
about the complexity of counting MAXCUT in planar graphs.
Exact Max 2-SAT: Easier and Faster p. 6
However, counting the ...
5
votes
1
answer
220
views
What is the (mixed strategies) equilibrium of this game?
Given a weight vector $w\in [0,1]^d$ such that $\sum w_i=1$, the game goes as follows:
Two players, $X,Y$ choose strategies $x,y\in [0,1]^d$ such that $\sum x_i = \sum y_i = 1$.
The utility (profit) ...
5
votes
1
answer
2k
views
Lovász $\delta$ condition for LLL Algorithm
http://en.wikipedia.org/wiki/Lenstra%E2%80%93Lenstra%E2%80%93Lov%C3%A1sz_lattice_basis_reduction_algorithm
What is the importance of the $\delta$ parameter for LLL bases called Lovász condition?
...
5
votes
1
answer
902
views
How much of P versus NP's difficulty stems from having to rule out the existence of Turing machines that "accidentally" solve, say, 3-SAT efficiently?
It seems like there is a sense in which a Turing machine that demonstrates P=NP could be said to "accidentally" exist. I'm wondering the extent to which the possibility of such machines is the main ...
5
votes
1
answer
264
views
What oracles make finding isomorphism (of finite structures) easy?
Below, all structures are finite, in a finite language, with underlying set an initial segment of the natural numbers. This has been edited to fix errors pointed out by Emil Jerabek in his answer ...
5
votes
1
answer
265
views
Approximation of Hamiltonian cycles
Let's define the $\texttt{MinHalfSimpCycle}$ search problem: Given $G=(V, E)$ a complete, undirected graph with weights on the edges. We want a simple cycle in $G$ (each vertex appears in it at most ...
5
votes
1
answer
175
views
Computational complexity of deciding if two elements are in the same cycle of a permutation
Given $n\in \mathbb{N}$, we have a bijection $P:\{0,1\}^n\to\{0,1\}^n$, i.e. $P$ is a permutation of $2^n$ symbols, $P\in S_{2^n}$. The permutation $P$ can be calculated efficiently, i.e. by a ...
5
votes
1
answer
276
views
NP-hardness of a sequence problem
Given $n$ binary sequences $s_i$ ($1\le i\le n$) with common period $T$. Let $s_i^{t_i}$ denote the sequence obtained by cyclically shifting $s_i$ for $t_i$ bits. The $n$ sequences form a good system ...
5
votes
1
answer
354
views
Fastest deterministic factoring algorithm in subexponential space?
Strassen's factoring algorithm shows that $\text{FACTORING} \in \text{DTIME}(N^{\frac{1}{4}+o(1)})$, but if I'm not mistaken in my analysis it also uses a similar amount of space. By making a trade-...
5
votes
1
answer
453
views
an algebraic variety for a boolean circuit
There is a polynomial reduction from a $3-CNF$ $SAT$ problem to some system of polynomial equations over $\mathbb{F}_2$.
I mean there is polynomial reduction $F$ such that for every boolean ...
5
votes
1
answer
488
views
Division by $n$ in elliptic curves
Let $E/\mathbb F_{p^m}$ be an arbitrary elliptic curve over the Galois field $\mathbb F_{p^m}$, and let $$[n]^{-1}(P)\cap E(\mathbb F_{p^m})=\{Q\in E(\mathbb F_{p^m})\mid nQ=P\}.$$ Also let $N=\#E(\...
5
votes
1
answer
384
views
Examples of Polyhedra with Large Shadows
Let $P \subseteq \mathbb{R}^n$ be a polyhedron described by $\mathcal{O}(n^{c_1})$ inequalities, where $c_1$ is a constant. Moreover, let $M\colon P \to \mathbb{R}^2$ be a linear mapping. I'm looking ...
5
votes
2
answers
604
views
Sets of vectors related by a rotation
We have a two sets of vectors ($\mathbb{C}^d$), $A=\{ v_1, \ldots v_n\}$ and $B=\{u_1, \ldots u_n\}$.
The question is if there is an efficient solution (polynomial in $n$) for checking whether $A$ ...
5
votes
1
answer
269
views
Simplices in convex polytopes
This question is a direct generalization of:
Counting the (additive) decompositions of a quadratic, symmetric, empty-diagonal and constant-line matrix into permutation matrices
Given a convex ...
5
votes
2
answers
371
views
What is the fastest way of finding a complement?
I am given a direct factor $N$ which is a normal subgroup of a group $G$. I want to find a complement of $N$ in $G$. The model of computation is RAM. It takes $O(n)$ time to find an inverse of one ...
5
votes
1
answer
178
views
Degree $d$ function with boolean inputs with small range is a junta?
Let $f : \{-1,1\}^n \rightarrow \{-1,1\}$ be a boolean function which is of degree at most $d$ when expressed as a multilinear polynomial ($f(x) = \sum_S \hat{f}(S) \prod_{i \in S} x_i$). It is known ...
5
votes
1
answer
183
views
Resource Constrained Routing with Refueling
What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...
5
votes
1
answer
245
views
What is Known About the Complexity of Calculating Minimal Surface Polyhedra?
I am currently ruminating about ways of generalizing Minimum Spanning Trees to Minimum Spanning "Hypertrees", where the cost is associated with simplex volumes and, where certain topological ...
5
votes
1
answer
644
views
The existential theory of the reals
Some definitions of the existential theory of the reals (ETR) allow a real closed field and some definitions allow only rational numbers as coefficients of polynomials. Which one is correct? Will the ...
5
votes
2
answers
2k
views
Bounding the minimal maximum norm of a solution of a linear system.
I would be grateful for pointing me out a reference to some general bound on the $\ell_{\infty}$ norm of a solution of a linear system. To be specific, suppose that we have an underdetermined linear ...
5
votes
2
answers
612
views
A Boolean function that is not constant on affine subspaces of large enough dimension
I'm interested in an explicit Boolean function $f \colon \{0,1\}^n \rightarrow \{0,1\}$ with the following property: if $f$ is constant on some affine subspace of $\{0,1\}^n$, then the dimension of ...
5
votes
2
answers
1k
views
Applications of minmax theorem(s)
Intro We suppose $X$ and $Y$ are nonempty sets and f: $X\times Y \rightarrow \mathbb{R}$. A minimax theorem is a theorem that asserts that, under certain conditions,
$$ \inf_Y \sup_X f = \sup_X \...
5
votes
1
answer
123
views
Algorithms to factorize words into product of powers
I came across this problem, which I guess is well known to combinatorialists of words, so I write here to see if someone can help me with some references.
Let $A$ be a finite set of symbols, are there ...
5
votes
1
answer
345
views
Decoding a Remark of Gödel on Complexity Theory
In Gödel's Collected Works (Vol 2), there is a discussion of von Neumann which was brought about by a query, made to Gödel, concerning the existence of a Turing machine which is so complex that its ...
5
votes
1
answer
213
views
Aperiodic set of corner Wang Tile [closed]
There is quite some reference on aperiodicity of the edge-type of Wang Tile. But I could not yet find aperiodic corner type of Wang Tiles... Could someone provide me some instances (better with ...
5
votes
2
answers
450
views
A simple language and systematic computations
The following somewhat popular simple computer language was enjoyed on sci.math, sci.math.research, pl.sci.matematyka, and perhaps before and after at several places (I wish I knew it's exact history)....
5
votes
1
answer
475
views
Maximal chain of 1s in binary strings
Let $S$ be the set of $2^n$ binary $n$-bit strings. For every $x\in S$, let $f(x)$ is the maximal chain of bits 1 in $x$. So Can we find a good upper bound of $$F(n)=\frac{\sum_{x\in S}f(x)}{2^n}$$
Of ...
5
votes
2
answers
584
views
Continuous Transportation Problem
Hi all, I'm trying to formulate an infinite linear program to prove optimality (via duality) for the Continuous Transportation Problem, e.g. the Kantorovich-Wasserstein distance. This is the ...
5
votes
1
answer
214
views
Graphs with Hermitian Unitary Edge Weights
Very recently, Hao Huang proved the Sensitivity Conjecture, which had been open for 30 years or so. Huang's proof is surprisingly short and easy. Here is Huang's preprint, a discussion on Scott ...
5
votes
1
answer
394
views
Explicit Formula of Delsarte's Linear Programming Upper Bound for $A_q(n,3)$
The problem of giving an explicit formula for $A_q(n,d)$ is sometimes referred to as "the main problem in coding theory." The value of $A_q(n,d)$ is given by the maximum number of codewords in a q-ary ...
5
votes
1
answer
148
views
Elliptic curves: for $P = aG$ for some $a$, what is $Q = a^{-1}G$?
Given an elliptic curve group with a generator $G$ where $G$ has a prime order, p.
Given a point $P=aG$ for some unknown $a$. Is it possible to efficiently calculate $Q=a^{-1}G$ without a discrete ...
5
votes
3
answers
422
views
Request for reference for some proofs about Gowers' norm
For any map $f : \mathbb{F}_2^n \rightarrow \mathbb{C}$ we define its $d^{th}-$Gowers' Norm (for $1 \leq d \leq n$) as, $\|f\|_{U^d(\mathbb{F}_2^n)}^{2^d} = \mathbb{E}_{L : \mathbb{F}_2^d \rightarrow \...
5
votes
1
answer
523
views
Finding sparsest solution of a linear system
I want to find the solution with most zero-components for the following problem:
$Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional ...
5
votes
1
answer
2k
views
Algorithm to minimally connect line segments in Euclidean plane
Suppose you have finitely many line segments in the Euclidean plane. How do you "connect them to form one chain of line segments of minimal length?"
More formally and generally, what I'm looking for ...
5
votes
1
answer
780
views
Algorithmic war
No, not the war on drugs, but the game of War considered in
Does War have infinite expected length?
As noted in that discussion, the game of war can go on forever, but my question is: can it be ...
5
votes
1
answer
271
views
Feasibility of linear programs
It's known that finding the intersection of n halfplanes in 2-d takes $\Omega(n\log n)$ time. Does the lower bound apply if we change the question to deciding whether the intersection is non-empty?