All Questions
1,808 questions
1
vote
0
answers
57
views
Reference request: Proof theory in $W_1^1$
Buss defined $V_2^1$ as a second-order bounded arithmetic corresponding to $\mathsf{PSPACE}$.
Later, Skelley introduced $W_1^1$, a third-order bounded arithmetic of $\mathsf{PSPACE}$.
Since the ...
- 11
1
vote
0
answers
28
views
Integral hull of a polyhedron Q is polyhedron
Let $Q \subseteq R^n$ be a rational polyhedron and let $Q_I=Convexhull(Q \cap Z^n)$. By finite basis theorem, we have $Q=P+C$ for some rational polytope $P$ and finitely generated cone $C$ where $C=R_+...
- 21
-1
votes
0
answers
41
views
Is it possible to backtrack an optimization solver? [closed]
I have an optimization problem and was using a linear programming optimizer to find solutions. However, I find that past a certain size, the problem becomes "infeasible" and has no solutions....
3
votes
0
answers
94
views
What is the smallest known number of states that a one-way cellular automaton needs to be universal?
We know there is an elementary cellular automaton (ECA) with 2 states (Rule 110) that is universal, i.e. Turing-complete. One-way cellular automata (OCA's) are a subcategory of ECA's where the next ...
- 121
0
votes
0
answers
57
views
Complexity of evaluation of analytic functions
Given an analytic function $f(x)$ (say as combination of elementary functions and operators), is it possible to compute $n$ first bits of the value of the function on the whole interval $[a, b]$ ...
- 67
0
votes
0
answers
21
views
Easy instance of set cover
I am trying to prove that a natural greedy algorithm solves the following instance of the set cover problem: for a set of elements $e\in U$ with a set of weights $w_e$, we define the cost of a subset ...
- 4,049
3
votes
1
answer
103
views
References: rigorous algorithms for elementary computations in base-b with complexity estimates
Definitions/Notation: Fix positive integers $b$ and $M$. Consider the set of real numbers which can be exactly expressed with $2M+1$ coefficients in base $b$, defined by
$$\mathcal{X}(b,M):=\{x\in \...
- 5,405
3
votes
0
answers
120
views
References on P vs NP under various axiomatic systems
I am teaching algorithms and theory of computation this semester and had the opportunity to dig a bit into the details of one way functions and the P vs NP problem.
This problem has resisted attacks ...
- 31
1
vote
1
answer
240
views
The equation $ax^2 +by^2 =1 \mod P$ in cyclotomic field
Let $L$ be a cyclotomic field, and $P$ a prime ideal of $\mathcal{O}_L$.
is there any symbol for the equation $ax^2 + by^2 =1 \mod P$ and if so, is it computable in polynomial time?
if $a$ is ...
- 133
7
votes
2
answers
242
views
Prove that $ n \leq d+1 $ under ordering constraints in $\mathbb{R}^d$
Let $x_1, \dotsc, x_n \in \mathbb{R}^d$ and $\theta_1, \dotsc, \theta_n \in \mathbb{R}^d$ be vectors such that for every $k \in [n]$, the following inequality holds:
$$
\langle x_k, \theta_k \rangle &...
1
vote
1
answer
217
views
What is the fastest known algorithm for evaluating a homogeneous binary polynomial?
This question was initially posted on math.stackexchange.com, but there is no appropriate answer, hence I have the right to publish it here again.
Let $f(x,y) = \sum_{i = 0}^d f_i x^i y^{d-i}$ be a ...
- 1,833
1
vote
0
answers
37
views
Computing all roots of a function with square-root terms
Given $3n$ positive numbers $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, and $x_1, \ldots, x_n$, we are given a function
$$f(x) = \sum_{i = 1}^n \frac{a_i}{\sqrt{(x - x_i)^2 + b_i}}.$$
Can we find all the ...
- 11
1
vote
0
answers
54
views
How computationally efficient are kernel tricks? [closed]
"If we compare to non-kernel polynomial regression it is O(Tnp) where is p is dimension of polynomial while kernel polynomial is O(n^2d) + O(T*n^2) where d is original number of attributes, ...
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
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 ...
- 21.2k
5
votes
1
answer
264
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 ...
- 53
2
votes
4
answers
212
views
Efficient algorithm for graph problem
Let $D=(V,E)$ be a directed graph, $S,T\subset V$ and $f:V\rightarrow \{1,\ldots, k\}$ a positive, bounded weight-function and $l\in \mathbb{N}$, find a path $v_1,\ldots, v_l\in V$ with $v_1\in S$ and ...
- 157
1
vote
1
answer
106
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 13
0
votes
0
answers
72
views
Klondike Solitaire as an NP-complete game
I am not a mathematician. I am trying to understand if the paper "The complexity of solitaire" that shows this game is NP-complete also has a implicit assumption that a given hand can only ...
- 1
0
votes
0
answers
37
views
Does the same hardness with access to different oracles imply equivalent oracles?
If $\textrm{coNP}^{\textrm{NP}}=\textrm{coNP}^{L}$ for $L\in\textrm{NP}$, then does that make $L$ NP-complete?
0
votes
0
answers
60
views
Understanding "A Note on a Theorem by Ladner"
I'm reading A Note on a Theorem by Ladner by Balcazar and Diaz, trying to understand the proof of Theorem 2.1. I don't know if it's just old notation, but I'm having quite a bit of trouble.
In step (...
1
vote
0
answers
114
views
Simultaneous elimination of variables in multiple polynomials
I have a system of $n=O(1)$ non-homogeneous polynomials of total degree $d=O(1)$ $p_1,\dots,p_r\in \mathbb Z[x_1,\dots,x_n]$. I would like to eliminate $n-1$ variables simultaneously from the $n$ ...
- 13.9k
1
vote
0
answers
92
views
Proof for non-existence of short integer program for squares
We do not know if $P=NP$ or not or if there is a superfast integer mutiplication algorithm. But I do not think either assumption is necessary to answer this question.
Is there a way to show within an ...
- 13.9k
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
3
votes
0
answers
146
views
Lower Bound of Solutions to P=NP?
Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with ...
- 3,029
1
vote
0
answers
69
views
Is it in theory possible to perform general Miller’s algorithm inversion as used with the optimal ate pairing with large trace in subexponential time?
Let’s I have the following :
2 curves $G_1$ defined on $F_p$ and $G_2$ being the $G_1$ curve’s twist defined on $F_p^2$ both having the same prime order ; a large trace ; and $F_p^{12}$ as their ...
- 87
2
votes
0
answers
95
views
Why cannot we adapt Barvinok type counting techniques to general convex integer programs?
Decision problems in Integer Linear Programming have Lenstra type algorithms (https://www.math.leidenuniv.nl/~lenstrahw/PUBLICATIONS/1983i/art.pdf) have been generalized to convex integer program ...
- 13.9k
0
votes
0
answers
122
views
Is it in theory possible to create a subexponential algorithm for solving discrete logarithms in multiplicative subgroups or within an Integer range?
As far I understand, when it comes to finite fields, Pollard rho and Pollard’s lambda are still the best algorithm for solving discrete logarithms in a multiplicative subgroup/suborder…
Index calculus ...
- 87
2
votes
0
answers
78
views
Is this variant of post correspondence problem undecidable?
The post correspondence problem, as defined by wikipedia, is undecidable. The problem is defined as follows.
Let $A$ be an alphabet with at least two symbols. The input of the problem consists of ...
- 21
-2
votes
1
answer
181
views
What is the computational complexity to verify a P solution with a deterministic Turing machine? [closed]
As we know, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is &...
- 3,084
4
votes
1
answer
221
views
Recent research on polynomial identities
I work in computational complexity, where I work on the problem of polynomial identity testing over arithmetic circuits. One particular case is when the variables over the polynomial ring don't ...
- 49
3
votes
1
answer
117
views
How to understand 'the problem of determining the exact number of monomials in P(x) given by a black box is #P-Complete'
In this paper:
Michael Ben-Or and Prasoon Tiwari. 1988. A deterministic algorithm for sparse multivariate polynomial interpolation, In: Proceedings of the twentieth annual ACM symposium on Theory of ...
- 31
2
votes
0
answers
93
views
How are moduli spaces related to geometric complexity theory?
I am interested in understanding the relationship between moduli spaces and geometric complexity theory (GCT).
Relation between moduli spaces and GCT:
How are moduli spaces related to geometric ...
- 29
3
votes
1
answer
315
views
About Shor's quantum algorithm
I know very little about quantum computing, and I've been trying to understand Shor's algorithm for the factorization of an integer $N$. I'm following Computational Complexity — a modern approach by ...
- 2,287
2
votes
0
answers
71
views
Lexicographically largest incidence matrix
I have simple algorithmic question, but I can't find any source where this algorithm is explained in details.
Let's assume that we have incidence (with 0 and 1 values) matrix of size $m\times n$. Let ...
- 501
0
votes
0
answers
48
views
A question on a quantitative form of Farkas' lemma
Suppose A is an $m \times n$ matrix whose entries are non-negative integers and $\mathbf{b}$ is a vector with rational entries. A version of Farkas lemma implies that if the equation $$A\mathbf{x}=\...
- 6,214
3
votes
1
answer
329
views
Nonexistence of short integer program sequence which generates squares
Is there a way to show within an integer program with constant number of variables and constraints of length $poly(\log B)$ (say length $\leq10^{1000000}\log B$), it is not possible for a variable to ...
- 13.9k
1
vote
0
answers
99
views
Minimum of the maximum element frequency given the family size and the universe size
[Crossposted at math.stackexchange].
Consider families of sets $\mathcal{F}$ with size $n = |\mathcal{F}|$ and universe $U(\mathcal{F})$ with size $q = |U(\mathcal{F})|$.
I have written and solved ...
- 988
8
votes
0
answers
164
views
Is there a substructure-preservation result for FOL in finite model theory?
It's well-known$^*$ that the Los-Tarski theorem ("Every substructure-preserved sentence is equivalent to a $\forall^*$-sentence") fails for $\mathsf{FOL}$ in the finite setting: we can find ...
- 21.2k
3
votes
2
answers
334
views
Algorithm to evaluate "connectedness" of a binary matrix
I have the following problem: given an $m \times n$ binary matrix $A$ like e.g. the following $9 \times 39$ matrix:
...
- 988
3
votes
1
answer
80
views
On the relationship between graph isomorphism and equivalence in ETL workflow dependency graphs
$\newcommand{\inn}{\mathrm{in}}\newcommand{\out}{\mathrm{out}}$Let $G = (V, E)$ and $G' = (V', E')$ be two DAGs representing dependency graphs of ETL workflows. Each node $v \in V$ (or $v' \in V'$) ...
user530362
9
votes
1
answer
506
views
Current state of the art in geometric complexity theory
I came across this interesting question from almost 7 years ago:
What are the current breakthroughs of Geometric Complexity Theory?
My question is quite simple: Have there been any breakthroughs in ...
0
votes
0
answers
115
views
Software for computing polytopes
As can be inferred from the title, I want to do some computation on the facets representation of the polytopes given the vertices. My advisor recommended me Polymake, which is indeed useful even with ...
- 1
1
vote
0
answers
50
views
Computational complexity of deciding if two elements are in the same cycle of a permutation, version 2
This question has relation with this previous one, although the two cases are not likely solved with the same method.
Let us consider a function $P:\{0,1\}^*\to\{0,1\}^*$ that can be calculated in ...
- 469
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 ...
- 469
5
votes
1
answer
176
views
Efficient counting of integer solutions to linear system
In my research, I have a particular 18x18 matrix $\mathbf{A}$ which defines the linear system $\mathbf{A}\cdot \mathbf{x} \leq \mathbf{-1}$ over the nonnegative integers. And I'm interested in ...
- 151
0
votes
0
answers
92
views
Algorithm that can solve or approximate the solution to a combination problem
I have a computational problem on my hands and I would like your help.
Here is my problem (simplified)
Let $X = \{x_1, x_2, \ldots, x_n\}$ represent a set of $n$ values.
Each value $x_i$ has a ...
- 1
13
votes
2
answers
555
views
Convergence of the sequence $s_{n+1}=s_n^2-s_{n-1}^2$
$s_{n+1}=s_n^2-s_{n-1}^2$, $s_0=\sqrt{x}$, $s_1=x$
This sequence seems simple, but is pretty confusing. If you try it with integers, you might think that it always diverges to infinity, but if you try ...
- 467
2
votes
0
answers
116
views
Reference for a coarse complexity notion
Throughout, I'm only interested in structures with domain $\mathbb{N}$, no primitive relations, and at least $0,\mathsf{Succ}$ as primitive functions. The length of $m\in\mathbb{N}$ is $\lfloor 1+\...
- 21.2k
2
votes
0
answers
172
views
NP-hardness of a string transformation problem with k templates
Given strings $x$ and $y$, a template length $l$, and a maximum number of different templates $k$, the task is to determine if it's possible to convert $x$ into $y$ using no more than $k$ different ...
- 21