All Questions
Tagged with computer-science computational-complexity
126 questions
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
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
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
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
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
173
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
8
votes
1
answer
3k
views
Polynomial-time quantum algorithms for lattice problems (GapSVP, SIVP, LWE)
The author of a recent preprint claims to have found polynomial-time quantum algorithms for solving the following lattice problems: the Decisional Shortest Vector Problem (GapSVP), the Shortest ...
- 157
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 ...
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
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 ...
- 81
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
0
answers
114
views
Computing sine of gamma function [closed]
In the sense of bit complexity, how difficult is it to compute $$\sin(a\Gamma(x))$$ where $a$ is a constant and $x>1$? Is it possible to avoid the computation of $\Gamma$ as first step?
Is there a ...
- 67
2
votes
0
answers
245
views
Pancake sorting problem – Is computing f(n) NP-hard?
The so-called Pancake flipping problem first discussed by Jacob E. Goodman here yields two entangled problems:
MIN-SBPR (Sorting By Prefix Reversals) - Given a permutation, find the smallest sequence ...
- 51
0
votes
0
answers
59
views
NC0 randomness vs. non-uniformity
In
Ajtai and Ben-Or. A theorem on probabilistic constant depth
Computations. STOC '84, 1984
Ajtai and Ben-Or show a non-uniform derandomization of BPAC0.
Is there a similar relation known for ...
4
votes
1
answer
362
views
Lower bound on the number of solutions of 2SAT
To compute the number of solutions of a 2SAT is a hard problem. Is there some nontrivial lower or upper bound on this number in terms of a “coarse-grained” description of the Boolean formula, for ...
- 1,207
3
votes
1
answer
167
views
Is factorial computation known to be in a class smaller than $FEXP$?
Functional version of the counting hierarchy is $FCH$. It is an open problem whether there a sequence of $poly(log(n))$ number of $+,\times$ operations utilizing the assistance of $O(1)$ number of ...
- 13.9k
0
votes
0
answers
104
views
Efficient Algorithm to Find Subset of Vectors Over $\mathbb{F}_q$ Living in Low Dimensional Subspace
Let $q$ be a fixed prime, $P, Q$ be polynomials with $\mathrm{deg}(Q) < \mathrm{deg}(P)$ and $h = O(\log n)$.
Let $S$ be a subset of $\mathbb{F}_q^n$ of size $P(n)$ such that there exists a subset ...
- 328
1
vote
1
answer
91
views
Algorithms for Polynomials Over a Real Algebraic Number Field, a reference
I need to find "Algorithms for Polynomials Over a Real Algebraic Number Field
Ph.D. thesis, University of Wisconsin, Madison (1974) by Rubald". However I cannot find it online nor in my ...
- 377
0
votes
1
answer
267
views
Algorithmically decide if an algorithm has optimal time complexity [closed]
Is there an algorithm with the following input and output?
INPUT: an algorithm computing a function $\mathbb{N}\to\mathbb{N}$. The algorithm is guaranteed to halt on all inputs.
OUTPUT: "YES"...
- 1
0
votes
1
answer
354
views
Maximize sum of edge weights on spanning tree
Problem: Given a complete graph with n vertices, the edge weight between vertex $i$ and vertex $j$ is $b[i]\times b[j]$.
Under the condition that the degree of point $i$ on spanning tree is DEG $[i]$, ...
- 11
3
votes
1
answer
311
views
Games and the right mathematical framework for GANs
Generative Adversarial Networks were introduced in http://papers.nips.cc/paper/5423-generative-adversarial-nets and has more than 20000 citations.
It is an important topic within deep learning.
Are ...
- 13.9k
1
vote
0
answers
47
views
Restriction of Rademacher Complexity
Let $F\subseteq C([0,1]^n,\mathbb{R})$ be a finite family of functions, which is non-empty. Let $A,B$ be subseteq of $[0,1]^n$, again non-empty, and let $Rad(C)$ denote the Rademacher complexity of ...
- 5,405
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 ...
- 367
1
vote
0
answers
144
views
Checking existence of proofs of fixed length
This question is a continuation of a related previous question (check here).
Let $\mathcal{L}$ be a recursive first-order theory with the Hilbert-Ackerman's proof calculus, and such that the ...
- 3,318
1
vote
0
answers
28
views
Modified straightline complexity of almost square of sums
Assume every linear operation (such as inner product with constant vector) can be performed in one step and multiplication by variables (quadratic operation) can be performed in one step.
We know the ...
- 1,826
3
votes
1
answer
96
views
What is known about computing all binary error correcting codes of given parameters?
Define a binary $(n, M, 2e + 1)$ code to be a code $C$ having $M$ code words in $\mathbb{F}_2^n$ whose minimum distance is $2e + 1$.
Are there any sources about using algorithms to find all given ...
- 143
4
votes
0
answers
76
views
Amortized complexity of P
Let $P$ be the class of all polynomial time computable functions from $\{0,1\}^*\rightarrow \{0,1\}$. For any $f\in P$, define function $f^A:\mathbb{N}\rightarrow \{0,1\}^*$ by
$$f^A(n)=(f(x_1),\cdots,...
- 509
1
vote
1
answer
237
views
Gröbner basis via integer programming
I have studied some papers related to solving integer programs via Gröbner bases. I wonder if the other way is possible or not — i.e., given any ideal, can we find the Gröbner basis by translating ...
2
votes
1
answer
120
views
Can quantum codes have more than $c \cdot \sqrt{N}$ correction distance for N encoding qbits?
I'm not an expert in quantum computing at all, but recently I've started to learn it (read Shen-Vyalyi-Kitaev's book and looked up some other literature here and there).
There are few remarkable ...
- 1,842
0
votes
1
answer
210
views
Is it theoretically possible to find a factoring algorithm that runs in polynomial time? [closed]
Given that we don't know if P=NP, what's to stop someone from finding tomorrow an algorithm that makes prime factoring, or any other trap-door function reversing for that matter, computationally ...
- 1
5
votes
1
answer
462
views
Polynomial size embeddings of toric varieties from polytopes?
Background: Let $P$ be a integral polytope, and $X_P$ the toric variety associated to the normal fan.
$X_P$ is always projective, because the collection of characters corresponding to the points $\...
- 1,462
3
votes
0
answers
155
views
Why does division parallelize but not continued fractions and is there an analog of multiplication to continued fractions?
All the basic arithmetic operations $\times,+,/,-$ can be parallelized. However continued fraction representation of a rational number is not parallelized. The process of Euclid's algorithm looks ...
- 13.9k
2
votes
0
answers
103
views
Buridan's principle in computable analysis
In (Lamport, 2012), Lamport proposes the principle
A discrete decision based upon an input
having a continuous range of values cannot be made within a bounded length of time.
I think it could be ...
9
votes
0
answers
2k
views
Exactly Counting the Number of Lattice Points in an $n$-Dimensional Sphere
Let $S_n(R)$ denote the number of lattice points in an $n$-dimensional "sphere" with radius $R$. For clarification, I am interested in lattice points found both strictly inside the sphere, and on its ...
- 311
3
votes
1
answer
262
views
What is known about this TSP variant?
Euclidian (planar) TSP asks for a tour with the minimum total length. The problem is known to be NP-hard. I am interested in the variant of finding a closed tour with the minimum enclosed area (...
- 2,993
5
votes
2
answers
285
views
Are there large integer matrices with entries computable in polynomial time, such that all minors are nonzero?
Is there a sequence of matrices $(A_n\in M_{2^n\times2^n}(\mathbb{Z}))_{n\in\mathbb{N}}$ such that the $(i,j)$th entry of $A_n$ is computable in polynomial time, such that all minors of each $A_n$ are ...
- 2,130
3
votes
1
answer
767
views
does recursive (decidable) languages closed under division (Quotient) with any language?
I need to prove or disprove that R languages are closed under divison.
I have managed to prove thet CFL are't closed under division. I read in wikipedia that RE languages are closed, but I didn't find ...
- 51
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
10
votes
2
answers
478
views
Most efficient reductions between NP-complete problems
Assume I need to solve an NP-complete problem, for which problem-specific methods (e.g. efficient heuristics or exponential algorithms faster than naive one) are not well developed. If the size of ...
- 781
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
20
votes
2
answers
2k
views
Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$
As we know, there are lots of consequences with the presupposition of the Riemann Hypothesis.
Similarly, are there any important consequences with the presupposition of $\mathbf{P} \neq \mathbf{NP}$ ?...
3
votes
2
answers
316
views
Should we expect there to be a problem that is PH-hard but not PSPACE-hard?
That is, is there a problem that all problems in the polynomial hierarchy can be reduced to in polynomial time, but which some PSPACE problem cannot be reduced to in polynomial time? Clearly if the ...
- 2,130
3
votes
1
answer
158
views
Matroids of hypercubes
Let $M_k$ be the (oriented) matroid of the $2^k$ points $B_k = \{-1, 1\}^k$ in $\mathbb R^k$. In other words, the (oriented) circuits of $M_k$ are the minimal (signed) linear dependences among $B_k$.
...
- 459
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 ...
- 51
4
votes
2
answers
155
views
Are there complexity classes X weaker than the linear time hierarchy such that any r.e. set is a coordinate projection of a set in X?
If $A\subseteq\mathbb{N}$ is recursively enumerable, then there is a $\Delta^0_0$ set $B\subseteq\mathbb{N}^2$ such that $A=\{x|\exists y\;(x,y)\in B\}$. $\Delta^0_0$ consists of exactly the sets in ...
- 2,130
4
votes
0
answers
155
views
Effective "almost enumeration" of monotone boolean functions
Denote by $\mathcal{M}(n)$ the set of all monotone functions $\{0,1\}^n \to \{0,1\}$.
Can $\mathcal{M}(n)$ be represented as $\mathcal{M}(n) = \{ f(t) | t\in \{0,1\}^k \}$ such that:
1) $k = \log |\...
- 2,576
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 ...
- 2,576
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
18
votes
1
answer
1k
views
Is it possible to make an algorithm that could predict the likelihood that a program will halt?
Today I began to read about computability theory. I do not even have an elementary understanding of the topic but it certainly got me thinking. I know there is there is no 'one-for-all' algorithm that ...
- 313