All Questions
1,809 questions
3
votes
0
answers
220
views
Algorithm for testing satisfiable fraction of linear equations mod 2
Hello
Let $F_{n,p}$ be a random process which generates a system of linear equations over $F_2$. The variables are $\{x_1, ..., x_n\}$ and for each of the $ \binom{n}{2}$ $i,j$ pairs, the equation $...
- 239
11
votes
1
answer
420
views
The complexity of the leading fractional bit of a power of a rational number
On a mailing list (math-fun) that I subscribe to Dan Asimov asked what's the most efficient way to calculate the leading decimal digits (say 10 of them) of $(p/q)^n \bmod 1$ where $p$ and $q$ are ...
- 4,636
1
vote
0
answers
282
views
Complexity of a problem related to 3D matching?
Given a set of triples of a base set $S$, find a subset of triples such that each element in $S$ appears exactly in one triple. This problem is NP-complete by reduction from NP-complete problem 3D ...
- 2,993
2
votes
1
answer
304
views
existence of l1 embedding using LP feasibility
hello
Let (A, d) be an n-point metric space
for $t \geq 1$,the task it to find an integer $m$ and an embedding $f : A \rightarrow R^m$ s.t.
$\forall x,y \in A$ : $d(x,y) \leq d_1(f(x), f(y)) \leq t*...
- 239
1
vote
1
answer
531
views
Split sum into equal terms
Given a sum of $l$ integers $r_1+...+r_k+...+r_l$ and an integer $t$.
Find indices
$1 < p_1 <...< p_h <...< p_{t-1} < l$
such that in sum
$(r_1+...+r_{p_1})+...+(r_{p_{h-1}+1}+......
- 11
0
votes
1
answer
561
views
FO complexity class
I'm currently in a theory of computing class and as such I have been looking up information about P vs NP and other complexity classes out of curiosity. In the process I cam across a blog post ...
- 133
6
votes
1
answer
357
views
computing abelianizations
Suppose I have a finitely presented group $G,$ and a subgroup $H$ of $G$ given by its finite generating set (given as words in the generators of $G.$ I want to know whether $H/[H, H]$ is finite. Is ...
- 96.4k
8
votes
2
answers
3k
views
How to find nearest lattice point to given point in R^n ? Is it NP ?
Consider some lattice in R^n.
Take some point "P" in R^n (which does not belong to this lattice in general).
What are the algorithms to find some nearest lattice point to "P" ?
"Nearest" - means in ...
- 24.9k
5
votes
2
answers
3k
views
Do you believe P=NP? [closed]
Do you believe P=NP?
I've seen some mathematicians say that if P=NP their work would be worthless and restricted to enunciating theorems. They seem to believe that there exist an almost philosophical ...
- 349
2
votes
4
answers
2k
views
Efficient algorithm for finding the minima of a piecewise linear function
Consider real numbers $a_i$ and $b_i$ for $i=1\dots n$ and define a function by
$f(x) = \max_i ( a_i + b_i x )$
We desire to find $\min_x f(x)$. Obviously this occurs at an intersection of two lines:...
- 823
2
votes
0
answers
227
views
Complexity of finding disjoint 2-factors with equal cardinality in cubic graphs?
Finding a connected 2-factor that contains every node in cubic graphs is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding vertex ...
- 2,993
8
votes
1
answer
790
views
Are problems in complexity theory dependent on set theory?
I was pondering the fact that maybe the classical hard complexity-theoretic questions are undecidable, not because they are so themselves, but because some set-theoretic foundations makes the ...
- 123
5
votes
0
answers
581
views
When is polytope compatible with network flow?
A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...
- 3,475
1
vote
3
answers
1k
views
best deterministic complexity for factoring polynomials over finite field
I would like to know currently what's the best deterministic complexity for factoring polynomials over finite field (without the assumption of GRH)? I have searched on google, there are many source, ...
- 1,109
1
vote
1
answer
522
views
What are the consequences of a polynomial time algorithm for finding out if a given number is expressible as the sum of two squares?
This question is based on this question, in which it is asked if there is a polynomial time algorithm which finds out if a given number is expressible as the sum of two squares. One of the answers ...
- 829
0
votes
1
answer
185
views
Derandomize on nondeterministic assumptions
Is there anyone prove the results such like the follows?
If $NP\not\subseteq BP(2^{\Omega(n)}),$ then $BPP\subseteq P^{NP}$
In summary, my question it that, can we get some derandomized results ...
- 57
3
votes
4
answers
4k
views
Existence of nonnegative solutions to an underdetermined system of linear equations
Similar questions have been asked elsewhere, but I think this is sufficiently different to warrant a new post. I have a particular matrix $A$ and would like to know when the system $Ax = 0$ has at ...
- 491
2
votes
1
answer
2k
views
Language in Space(n) but not in NP
For $lim_{n \rightarrow \infty} \frac{ f(n) \log n } { g(n) } = 0$
we can construct languages in $DTime(g(n))$ but not in $DTime(f(n))$.
We know how to prove $Space(n) \neq NP$. Since $x \Rightarrow ...
- 663
2
votes
0
answers
535
views
Undecidability, Church Turing Thesis, and P/poly
I find the following three facts individually acceptable, but together deeply unsettling:
1) P/poly can decide the unary language $\{ 1^n | M_n(n) \quad \text{halts} \}$ via advice string.
2) Church ...
6
votes
3
answers
11k
views
Maximum flow with negative capacities?
I'm trying to compute an (s-t) maximum flow through a network which includes a number of arc pairs ((u,v), (v,u)) that have equal, negative capacities (weights). I'm not aware of any efficient ...
- 83
4
votes
4
answers
703
views
efficient way to compute the inversion of the following matrix
Hi, there
I have looked it up in the current textbook. The conventional numerical method to compute the inversion of an $n \times n$ matrix requires $O(n^3)$. However, for the following special ...
- 41
2
votes
1
answer
646
views
No complexity class contains all recursive languages
I want to prove that there does not exist some complexity class that contains all recursive languages.
Any complexity class C is defined by a complexity measure $\Phi$ (according to Blum axioms) and ...
- 31
5
votes
2
answers
680
views
Finding the solution to b = Ax that minimizes the Hamming weight (everything over the field F_2).
Is there an efficient algorithm for finding the solution $x$ of
$b = Ax$
that minimizes the Hamming weight of $x$, where
$A$ is a nxm-matrix over the field $\mathbb{F}_2$ ("integer matrix modulo 2")...
- 141
0
votes
1
answer
427
views
Is the following statement a correct formulation of the (much doubted) P = NP conjecture?
"Call a Turing machine $A$ a d-machine if, for some polynomial $p(\cdot)$, when $A$ starts with any input string, say of length $n$, in its alphabet on its (otherwise blank) tape, it will halt in a ...
- 2,437
3
votes
2
answers
4k
views
Complexity of convex quadratically constrained quadratic programming (QCQP)
Could someone tell me the time complexity of a convex quadratically constrained quadratic program (QCQP)? Any references?
- 145
1
vote
1
answer
366
views
"NP has linear circuits" --> something interesting? [soft, philosophical, open]
Page 121 of Computational Complexity, A Modern Approach states:
6.11 (Open Problem) Suppose make a stronger assumption than $NP \subset P/poly$: every langauge in NP has linear size circuits. Can we ...
3
votes
1
answer
316
views
Class Separation, Oracles, Relativization
It is known, there exists oracles A, B s.t.:
$P^A = NP^A; P^B \neq NP^B$, showing that any proof of P vs NP must be non-relativizing.
Questions:
(1) Can we actually use Oracles to separate ...
- 663
7
votes
2
answers
2k
views
Why is "P = NP implies EXP has circuit of $2^n/n^" interesting? [Soft, Philosophical]
For example, "P=NP implies PH=P" is interesting ... because most of us don't believe PH=P, so it provides strong evidence P != NP.
On other hand, "P=NP implies EXP has circuit of $2^n/n$ size" seems ...
12
votes
1
answer
2k
views
Computing exponential sums rapidly?
I am looking at sums of the form
$\sum_{N\le n \leq N+M} e(P(n))$
where $P\in R[x]$ is a polynomial of bounded degree. Let's say $M\sim c N$ (and $N$ is large).
The question is - when can one ...
- 20.2k
6
votes
2
answers
908
views
A Query regarding the Halting Problem (Omega): Halting Probability for Given Input Size
I was studying the Halting Problem in context of the Probability and had a few doubts regarding it. Hope someone could help me out.
I am aware of the probability of a Random program halting on a ...
- 81
2
votes
2
answers
500
views
We know that a permutation of N bits {0, 1}^N --> {0,1}^N can be computed by circuits of size O(n 2^n). But are there circuits that can be computed only by size O((n^2)(2^n) and not O(n 2^n)
We know that a permutation of N bits {0, 1}^N --> {0,1}^N can be computed by circuits of size O(n 2^n). But are there circuits that can be computed only by size O((n^2)(2^n) and not O(n 2^n)
- 21
47
votes
3
answers
12k
views
Testing whether an integer is the sum of two squares
Is there a fast (probabilistic or deterministic) algorithm for determining whether an integer $n$ is a sum of two squares?
By "fast" here I mean polynomial time (i.e. time $O((\log n)^{O(1)})$). Note ...
- 20.2k
5
votes
5
answers
3k
views
Oracle, Relativization, and P vs NP, [Philosophical]
I can understand why $P^A = NP^A$ does not imply $P=NP$, $A$ can "contain" the powers of NP.
However, why does $P^B \neq NP^B$ not imply $P \neq NP$? It seems like if $P$ and $NP$ denote the same ...
- 663
4
votes
1
answer
242
views
Growth of Functions
Does there exist a function f s.t.:
(1) $f(f(n)) \in O(f(n))$
(2) $f(n) \in \Omega(\cup_i n^i)$
Thanks!
- 663
8
votes
3
answers
1k
views
P vs. NP resistant problems
According to Stephen Cook on wikipedia, http://en.wikipedia.org/wiki/P_versus_NP_problem
...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a ...
- 26.9k
3
votes
1
answer
2k
views
P = NP -> EXP has circuit size O(2^n/n)
How does this proof work / can someone provide a link to a paper? This is exercise 6.7 of Computational Complexity a Modern Approach. I know the following:
(1) P = NP -> EXP = NEXP (by padding)
(2) ...
- 663
31
votes
4
answers
3k
views
Algebraic P vs. NP
I recently attended a lecture where the speaker mentioned that what he was talking about was connected to the algebraic version of the $P$ vs. $NP$ problem. Could someone explain what that means in a ...
- 42.9k
4
votes
1
answer
394
views
Palinderome in single tape TM in O(n^2)
It is known that:
(1) Palindrome can be recognized by two-tape TM in O(N)
(2) Palindrome can be recognized by one-tape TM in O(N^2)
Question: do we actually have proof that a one-tape TM can't ...
- 663
1
vote
2
answers
3k
views
"P vs NP" and "NP vs P/Poly"
It is known
$P \subset P/poly$
$NP \not\subset P/poly \Rightarrow P \neq NP$
However, do we have a proof of:
$P \neq NP \Rightarrow NP \not\subset P/poly$ ?
I.e. is there a world where $P \neq NP$, ...
- 663
54
votes
2
answers
8k
views
Walsh Fourier transform of the Möbius function
This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly orthogonal to Morse
August Ferdinand Möbius (November 17, 1790 – ...
25
votes
3
answers
3k
views
Discrete Fourier Transform of the Möbius Function
Consider the Möbius function $\mu (m)$. (Thus $\mu(m)=0$ unless all prime factors of $m$ appear once and $\mu (m)=(-1)^r$ if $m$ has $r$ distinct prime factors.) Next consider for some natural number $...
- 24.7k
3
votes
1
answer
2k
views
Why is UHALT in P/Poly?
My textbook claims: P \subset P/Poly, and that this is proper.
It claims that all unary languages are in P/Poly, and then goes on to claim that UHALT = {1^n | n encodes (M,x) s.t. M halts on x } is ...
- 663
1
vote
1
answer
2k
views
Proving APSPACE = EXP [closed]
AP = Alternating Polynomial Time
PSPACE = Polynomial Space
APSPACE = Alternating Polynomial Space
EXP = Exponential time
Proving AP = PSPACE is fairly easy:
1) TQBF is PSPACE complete
2) AP can ...
- 663
3
votes
1
answer
266
views
A question about the "information-content" of a very simple type of Turing machine.
All the Turing machines we consider have (1) a two-way infinite tape (2) one and only one halting
state (3) an alphabet of exactly two symbols-"1" and " "(or "blank"). Let n be any positive integer.
...
- 6,215
4
votes
0
answers
242
views
Domination in Nice Lattices
Let an integer vector be nice when it has only two nonzero components, which sum to zero. So (0, 0, 3, 0, -3) and (-1, 0, 1, 0, 0) are examples of nice vectors in $n=5$ dimensions.
Call a lattice ...
- 1,288
12
votes
2
answers
10k
views
NP not equal to SPACE(n)
Exercise 3.2 of Computational Complexity, a Modern Approach states:
Prove: NP != SPACE(n) [Hint: we don't know if either is a subset of the other.]
I don't know how to solve this problem.
It's in ...
- 663
10
votes
5
answers
645
views
Syntactically capturing complexity classes
Primitive recursive functions are syntactically constructible in the sense that from a set of "axioms" we can build every function in the set $PR$. This basicly means that we can build a machine that ...
user10891
1
vote
1
answer
7k
views
Finding the square root modulo n, when the factors of n are known
Last month, I asked whether there is an efficient algorithm for finding the square root modulo a prime power here: Is there an efficient algorithm for finding a square root modulo a prime power?
Now, ...
- 2,649
44
votes
4
answers
5k
views
Why is "P vs. NP" necessarily relevant?
I want to start out by giving two examples:
Graham's problem is to decide whether a given edge-coloring (with two colors) of the complete graph on vertices $\lbrace-1,+1\rbrace^n$ contains a planar $...
- 25.5k
3
votes
2
answers
342
views
Abstract notion for energy complexity of computational problems?
Energy is very valuable computational resource especially in mobile computing. Optimizing the energy consumed during the execution of algorithms has significant practical implications. Intuitively, It ...
- 2,993