Questions tagged [cc.complexity-theory]
P versus NP and other resource-bounded computation.
0
votes
0answers
56 views
Can be converted UNAE3SAT into a P-complete decision problem?
By Self-reducibility, we understand that a search problem can be reduced to the self problem but by a decision problem instead of a function problem. P is trivially self-reducible, but what about P-...
-2
votes
0answers
22 views
Complexity of a Subset Sum variant with target dependent on elements
I would like to know whether the following problem is NP complete:
For a set $S = \{(a_1,b_1,\delta_1),\ldots,(a_n,b_n,\delta_n)\}, a_i,b_i,\delta_i \in \mathbb{N}$.
Does $\exists ~S^{'} \subseteq S$ ...
9
votes
1answer
203 views
What is the reference for the proof Gödel's first incompleteness theorem based on the undecidability of the halting problem?
A weaker form of Gödel's First Incompleteness Theorem, direct proofs of which in Gödel's manner are lengthy, involved and at some place rather counter-intuitive, has a simple and intuitive proof based ...
0
votes
0answers
65 views
Where is the flaw in this proof that an LP solves TSP? [duplicate]
In this preprint on Arxiv, M. Diaby, M.H. Karwan, and L. Sun give a Linear Program which they claim solves the Traveling Salesman Problem. In contrast to their prior work, which was asked about here, ...
1
vote
1answer
70 views
Computational hardness for sampling a uniform matching
A famous result of Jerrum, Sinclair, and Vigoda shows that there exists a polynomial-time algorithm which takes a bipartite graph $G$ and produces a random perfect matching $M$ of $G$ (assuming one ...
6
votes
0answers
113 views
Can reciprocal inputs speed up monotone computations?
A $(+,\times,1/x_i)$ circuit is a standard monotone arithmetic $(+,\times)$ circuit with the only difference that now besides the input variables $x_1,\ldots,x_n$, also their reciprocals $1/x_1,\...
2
votes
1answer
135 views
An equation relating Time complexity, Space complexity, and entropy of output
Is there an equation that relates minimum time complexity, minimum space complexity, and entropy of the output of a function? It seems to me that there should be a relatively intuitive relationship ...
-2
votes
1answer
95 views
Does P^NP=NP imply NP=coNP? [closed]
If you have it, the proof would be appreciated.
Note: P^NP means P with NP oracle
2
votes
0answers
65 views
Best algorithms for real linear programming
Linear Programming asks for $x\in\mathbb R^n$ such that $Ax\leq L$ holds where $A\in\mathbb R^{m\times n}$ and $L\in\mathbb R^m$ are given. Karmarkar has shown that $\ell$ is the number of bits of ...
2
votes
0answers
60 views
Complexity of counting Wang tiles
Consider the question of counting Wang tilings on a torus. The decision version of this problem is known to be NP-complete. Is the counting version #P-complete?
-2
votes
0answers
58 views
2
votes
0answers
48 views
How to improve this pseudorandom generator?
Let $f$ be a Boolean function and $\varepsilon > 0$.
There exists a pseudorandom generator $G_f: \{0,1 \}^{n^{\varepsilon}} \to \{0,1 \}^n$ with the following property.
Let $T$ be a set and $...
2
votes
1answer
58 views
Weighted Min-Cut in bounded-genus graphs
What is the status of the following decision problem ?
Input : A graph $G=(V,E)$ embedded in a torus (or more generally a surface of genus $g$), a weight function $w:E \rightarrow \{-1,1\}$
Output : ...
2
votes
0answers
52 views
Is #PP2DNF hard to approximate?
The problem #PP2DNF asks to count the number of satisfying assignments of a positive partitioned 2-DNF Boolean formula, i.e., a formula $\phi$ on variables $X_1, \ldots, X_n, Y_1, \ldots, Y_m$ of the ...
2
votes
1answer
116 views
Would an NP-complete public key cryptosystem imply NP=co-NP?
Would the existence of an NP-complete (or co-NP-complete) public key signature cryptosystem imply that NP = co-NP? My specialty is definitely not theoretical computer science, so this is somewhat of ...
5
votes
2answers
101 views
Concrete examples of $\sharp P_1$ complete problems? Self avoiding walks?
The only examples of $\sharp P_1$ complete problems I've seen are fairly abstract : e.g. here https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf
Valiant proves that there exists a $\...
3
votes
0answers
52 views
Conjugacy testing problem
The below-given problem is in black box setting means input is given by set of generators.
Given an abelian $p$-group $A$ and two matrices $U_1$ and $U_2$ in $R(A)$ such that the order of $U_1$ and $...
2
votes
0answers
91 views
Why is counting the number of hamiltonian subgraphs $\sharp P $ hard?
I'm confused about how to prove either of the following closely related statements. They are both from this paper: https://epubs.siam.org/doi/10.1137/0208032
1) "A further problem that can be shown ...
9
votes
1answer
150 views
Natural candidates for NP-E and E-NP
It has been known since the early 70's that ${\bf NP}$ and ${\bf E}=DTIME(2^{O(n)})$ are not equal (because ${\bf E}$ is not closed under polynomial-time many-one reductions, in contrast to ${\bf NP}$...
-4
votes
0answers
94 views
Find algorithm for statiscits problem find all solutions if exist
please i am trying find algorithm for 3 months but unsuccesful, i asked my teaches of theretics informatics but unsuccesfull too.
problem.
for example my Mum give me 50€ with condition -> can spend ...
5
votes
1answer
139 views
Viola's Reduction of 3XOR to listing triangles
Apparently this was due to Pătraşcu, but in this report on the ECCC server, Viola states that 3XOR can be reduced to listing triangles.
Assume that given a graph in adjacency list format, with $m$ ...
2
votes
2answers
128 views
Is S-T CONNECTEDNESS #P-complete on instances when all s-t paths are of the same length?
S-T CONNECTEDNESS
Input: a (undirected) graph $G=(V,E)$; $s,t \in V.$
Output: number of spanning subgraphs of $G$ in which there is a path from $s$ to $t$.
S-T CONNECTEDNESS problem is known to be #...
-3
votes
2answers
159 views
Do Turing complete languages automatically have efficient algorithms [closed]
Every Turing complete programming language can describe an algorithm that sorts sequences. Is it also true that every Turing complete language can describe an algorithm that sorts sequences in $\...
13
votes
1answer
419 views
Is there a P-complete language X such that succinct-X is in P?
I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...
5
votes
2answers
287 views
Is this partition problem strongly NP-complete?
Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the ...
2
votes
0answers
151 views
Best polynomial-time approximation factor for NP-optimization problems
Let us say that a function $f(n)$ is the best approximation factor for an NP-optimization problem, if both of the following hold:
There exist a polynomial-time algorithm $A,$ and an integer $n_0$, ...
8
votes
0answers
95 views
Does ${\bf CFLPAD}={\bf PPAD}$?
What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a (non-)deterministic finite/push-down automaton encodes the problem?
I asked a similar ...
0
votes
1answer
106 views
Permuting the columns of a 0/1-matrix to avoid short segments
Consider an $n \times n$ table with $n$ stars such that each row contains at most $\log n$ stars. The stars break each row into segments (continuous parts of a row without stars). Let's call a segment ...
5
votes
1answer
154 views
Minimal information needed for determine some function
From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of ...
-4
votes
2answers
79 views
Is it possible to have a sorting algorithm that computes faster than QuickSort? [closed]
Given an unsorted array, QuickSort has to touch each source element it is trying to sort multiple times before it declares an array as sorted.
(notice how many times the 2 is touched [circled in red ...
7
votes
0answers
110 views
Can relativization technique be applied to natural NP-complete languages?
Levin [1] defined distNP is the distributional problem (L,D), where L ∈ NP, and D is an ensemble of efficiently samplable distributions over problem instances. We say that a distNP problem (L,D) is ...
1
vote
0answers
43 views
Are there any continuous-time stochastic processes in which transition probabilities are discontinuous functions over time? [closed]
In stochastic processes, like homogeneous Markov processes, Poisson processes, Queueing systems etc., the functions that represent (transition) probabilities are continuous over time. This is also ...
2
votes
1answer
201 views
Deciding whether a graph contains a complete balanced bipartite graph
Is it known whether the following problem is in P or is NP-complete?
Problem: given an input graph $G$ on $n$ vertices, decide whether $G$ contains a complete $n/2 \times n/2$ bipartite graph.
3
votes
0answers
73 views
Fixed dimension Linear Integer Programming in $NC$
We know if fixed dimension linear integer programming is in $NC$ then integer $GCD$ is in $NC$. Is this the only non-trivial implication of fixed dimension linear integer programming in $NC$?
1
vote
0answers
267 views
EXPSPACE proof and its implications
I'm dealing with the min-max regret 0-1 Integer Linear Programming problem (MMR-ILP, for short), which is formulated as below.
\begin{equation} \label{eq:nip_obj}
\min_{x \in \Phi} \sum_{i = 1}^n ...
4
votes
1answer
136 views
Complexity of Acyclic Hypergraph Isomorphism
It is well known that the graph isomorphism problem restricted on trees is much easier than the general case. It can be done in logarithmic space (Jenner B, Lange KJ, McKenzie P. "Tree isomorphism and ...
1
vote
1answer
84 views
Is balanced Hamiltonian cycle NP complete on maximal plane graphs?
I know that the Hamiltonian cycle is NP complete on the class of maximal plane graphs.
If we instead ask about balanced Hamiltonian cycles (i.e. same number of faces on both sides) on maximal plane ...
1
vote
0answers
62 views
Complexity of enumerating over promise problems and circuits?
Given an enumeration over all Turing Machine which run with increasing length, is there a ``complexity class'' which describes the complexity of determining whether a given TM satisfies the promise ...
11
votes
0answers
116 views
Can two-tape read-only Turing machines recognize any recursive language?
Suppose that a $k$-tape read-only Turing machine receives its input on each $k$ tapes.
It cannot write on the tapes, but it can move on them in both ways, even move off from the input.
So for example, ...
11
votes
1answer
237 views
Is DSPACE(n) = DSPACE(1.5n)?
From space-hierarchy theorem it is known that if $f$ is space-constructible then
DSPACE($2f(n)$) is not equal to DSPACE($f(n))$.
Here, by DSPACE($f(n))$ I mean the class of all problems that can ...
2
votes
1answer
387 views
Possible to do Complexity theory with only counting and Pigeonhole
Most of the proofs in the book Computational complexity by Barak and Arora seem to be Pigeonhole in disguise. What are some places in Complexity theory where counting and Pigeonhole was insufficient ...
5
votes
1answer
237 views
Is Murphy's Law of Complexity Theory consistent? What separations/collapses does it imply?
A decade ago I observed what I dub "Murphy's Law of Complexity Theory": whenever a new separation or collapse is discovered, the question is answered in the direction that makes $P\overset?=NP$ most ...
-2
votes
1answer
116 views
Why $PSPACE!=Dtime(2^n)$? [closed]
Why $PSPACE != Dtime(2^n)$? I can not see how padding argument can help here, how can it be proven?
9
votes
1answer
128 views
Best known asymptotic PCP sizes / 3-SAT
What are the best known asymptotic upper bounds on sizes of probabilistically checkable proofs? Ideally, I am looking for a contemporary survey on this broad question, but if there is none, I am ...
10
votes
0answers
95 views
Complexity of checking $a > br^m + cr^n$, with $r$ rational
I'm wondering if the following problem is decidable in P-time (or even NP):
Given $a, b, c \in \mathbb{Z}$ and $m, n, p, q \in \mathbb{N}$ all in binary, decide if $a > br^m + cr^n$, where $r = {p ...
2
votes
1answer
99 views
Minimization version of matrix p-norms?
I considered a minimization version of matrix p-norms, defined for a matrix $A$ by
$$
f_p(A)= \min_{x\neq 0} \frac{||Ax||_p}{||x||_p}.
$$
Notice that $f_p(A) = 0$ if and only if $A$'s columns are ...
1
vote
1answer
237 views
$P=BPP$ without good PRGs?
We know that the existence of good pseudorandom generators (PRGs) does not only imply $P=BPP$, but also $PromiseP=PromiseBPP$.
Let us assume $PromiseP\ne PromiseBPP$. Then good PRGs do not exist. ...
5
votes
1answer
106 views
Complexity of counting integer roots of multivariate polynomials in a polyhedron?
Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials in $\mathbb Z[x_1,\dots,x_m]$ with both $m$ and total ...
4
votes
1answer
68 views
Complexity of finding Exact Size Cut-Sets in Bipartite Graphs
I am interested in the problem of deciding if a cut-set of a given size $k$ (i.e. the number of edges crossing the partitions is $k$) exists in a given bipartite graph (both the graph and $k$ are part ...
10
votes
1answer
356 views
What is the complexity of this game?
This is a generalization of my previous question.
Let $M$ be a polynomial-time deterministic machine that can ask questions to some oracle $A$. Initially $A$ is empty but this is can be changed after ...
