All Questions
1,809 questions
13
votes
6
answers
3k
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 ...
- 236k
0
votes
0
answers
39
views
Max-flow modeling with unified vehicle and commodity variables
I am working on a network flow problem that involves routing through a time-space network. The network consists of:
A single source node and a single demand node.
A fleet of vehicles with specified ...
- 63.9k
12
votes
2
answers
980
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,713
4
votes
0
answers
155
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 ...
- 2,993
1
vote
0
answers
87
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 ...
- 2,287
1
vote
0
answers
126
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 ...
- 4,677
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,446
3
votes
1
answer
807
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 ...
- 43
0
votes
0
answers
30
views
Application of greedy approach for optimization
I want to maximize an objective given by $$\max_{\{q_n,p_n\}} \sum_{n=0}^\infty (\alpha_1 - \beta_1 n) p_n + (\alpha_2 - \beta_2 n) q_n$$
where $\alpha_1 > \beta_1 >0$ and $\alpha_2 > \beta_2 ...
- 23
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
96
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 ...
- 1,284
8
votes
2
answers
1k
views
Minesweeper as a linear algebra problem
I've written a computer program to generate and solve minesweeper games. Once I've eliminated the obvious mines and safe squares I look at each remaining connected setsin turn and formulate a linear ...
- 99
8
votes
4
answers
890
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 ...
- 1,446
2
votes
1
answer
213
views
Is matrix B obtained from matrix A?
Assuming a matrix $\mathbf{A} \in \mathbb{R}^{4096 \times 4096}$ sampled from a standard normal distribution $N(0, 1)$, and another matrix $\mathbf{B} \in \mathbb{R}^{4096 \times 4096}$ either sampled ...
- 49
13
votes
1
answer
399
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 \...
- 181
3
votes
0
answers
125
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,367
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 ...
9
votes
2
answers
843
views
How did they come up with the MRRW bound?
Among the good asymptotic bounds in coding theory in the MRRW bound. It is obtained by using the linear programming problem of Delsarte's and providing a solution. The LP problem is
Suppose $C \...
- 232
21
votes
3
answers
7k
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 ...
- 19.6k
0
votes
0
answers
36
views
ILPs with square constraint matrix
Given the Integer Linear Programming ($\text{ILP}$) problem
\begin{array}{ll}
\text{minimize} & c^T x \\
\text{subject to}& \mathbf{A}^T x \ge b \\
\text{where}&c,x,b\in\mathbb{N}_0^n,\\ &...
- 13.2k
3
votes
0
answers
85
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 ...
- 3,549
1
vote
0
answers
49
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(...
- 518
2
votes
0
answers
119
views
Seeking insights on bounded set positive solutions for a set of linear systems in $\mathbb{R}^n$
Before delving into my query, I'd like to provide some context. Consider a continuous function $f:\mathbb{R}^{k}\rightarrow\mathbb{R}^{m}$ and a compact set $\mathcal{B}\subset \mathbb{R}^{k}$ (...
0
votes
0
answers
16
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 $...
- 21
1
vote
0
answers
68
views
Fundamental regions in convex programming
In linear programming, the fundamental regions are polyhedra, since those are the intersection of half-spaces defined by linear inequalities. In semidefinite programming, the fundamental regions are ...
0
votes
0
answers
26
views
Monotony of enforced subtour merging
Is it true that for a symmetric TSP instance in the sequence of edges generated by successively:
calculating the optimal 2-factor
adding cardinality constraints on the edgesets of the 2-factor's ...
- 5,429
14
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 ...
- 1,446
0
votes
0
answers
171
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 ...
- 5,429
4
votes
0
answers
214
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 ...
- 24.2k
3
votes
1
answer
308
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 ...
- 81
0
votes
0
answers
64
views
Alternatives to McCormick Envelope
I have an optimization problem for which I have the optimal solution obtained by the ILP.
However, when I introduced the McCormick Envelope to replace the product of a bi-linear term in its LP ...
- 3,065
1
vote
0
answers
168
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 &...
- 1,171
30
votes
5
answers
14k
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?
- 1,590
0
votes
1
answer
169
views
How to integrate an indicator function/constraint into the cost function of a linear program?
I have a mathematical model $P$ for which I optimize two cost functions say $F_1$ and $F_2$ subject to a set of constraints $C1$–$C10$.
In $F_2$, I want it to be included only when its expression ...
- 5,429
15
votes
0
answers
487
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 ...
- 540
2
votes
1
answer
216
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 ...
- 1,171
0
votes
0
answers
67
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,171
1
vote
0
answers
52
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?
- 13.2k
7
votes
1
answer
268
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 ...
- 1,171
3
votes
0
answers
93
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 ...
- 1,171
0
votes
0
answers
164
views
Inf-convolution of norm 1 and norm 2 square
The inf-convolution of the functions $f$ and $g$ defined on $\mathbb{R}^n$ is
$$
h(x)=\inf _{y \in \mathbb{R}^n} f(y)+g(x-y) .
$$
We can prove that if $f,g$ are convex functions, then $h$ is convex.
...
- 35.5k
2
votes
1
answer
92
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.
- 25.4k
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 ...
- 63.9k
4
votes
1
answer
248
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 ...
- 21.1k
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 ...
- 4,671
0
votes
1
answer
28
views
Calculating vertex potentials from optimal matchings
Question:
can the solution to the dual of a Linear Program be calculated directly from the solution of the primal Linear Program?
If yes, what are known algorithms and their bounds on complexity.
As ...
- 5,429
2
votes
0
answers
81
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 ...
- 153
1
vote
0
answers
116
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''...
- 9,330
1
vote
1
answer
98
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 ...
- 21.1k