# Questions tagged [cc.complexity-theory]

P versus NP and other resource-bounded computation.

2,657 questions
Filter by
Sorted by
Tagged with
163 views

### $\exists \mathbb R$ and IP

We know NP$\subseteq$ $\exists \mathbb R$$\subseteq$ PSPACE=IP, but is there some more direct proof for $\exists \mathbb R\subseteq$ IP? What about the other direction, are there some Arthur-Merlin ...
81 views

### Minimum cut with nonlinear objective function

Let $G$ be an undirected graph. The classic minimum (cardinality) cut problem asks for a cut $C\subseteq E(G)$, such that $|C|$ is minimum. Let us generalize it the following way: let $f$ be a ...
90 views

### Counting quotient graphs, but not exactly

All graphs considered will be directed graphs $G=(V,E)$, with $E \subseteq V \times V$ (so possibly with self-loops). For $k \in \mathbb{N}_{\geq 1}$, I will write $[k]$ the set $\{1,\ldots,k\}$. A $k$...
2k views

### Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates

Let $f$ be a Boolean function and let's think about f as a function from $\{-1,1\}^n$ to $\{ -1,1 \}$. In this language the Fourier expansion of f is simply the expansion of f in terms of square free ...
153 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 ...
163 views

### Does Hadwiger conjecture imply that NP = coNP?

(Disclaimer: I suspect the answer is no, but I fail to see why) Here is a nice picture by David Epstein (taken from Wikipedia) illustrating Hadwiger's conjecture: The point is that if in a given ...
120 views

### Canonical complete problem for $\mathrm{FP}^{\Sigma^p_2}$

Given a $\Sigma^p_2$-complete oracle (i.e., $\Sigma_2 \mathrm{SAT}$), I have a problem that requires to call this oracle polynomially many times and returns an integer. Essentially, this is a function ...
52 views

### Complexity of comparing extended integer power towers

Inspired by this stackexchange question, is it an open problem to compare two power towers of positive integers if we additionally allow numbers lower in the tower to themselves be represented by ...
158 views

### How small can extension complexity be?

In this article on extension complexity of regular polygons https://arxiv.org/pdf/1505.08031.pdf it is mentioned that extension complexity of $n$ regular polygons should be $\theta(\log n)$. This is ...
66 views

### Complexity status of the Edge Deletion problem to bounded degree graphs

I'm interested in the complexity status of the following problem. Input: a graph $G=(V,E)$ and two natural numbers $k$ and $d$. Output: Yes, if there exists a subset $E' \subseteq E$ of cardinality ...
616 views

### Strongly NP-complete variants of subset sum or partition problem

Some problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's GI result). However, the fixed-point free GA ...
83 views

### Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands

Has anyone studied the asymptotics of problems in complexity classes like $BPP$? The thought came to me that if a problem in $BPP$ only requires $O(log(n))$ bits of entropy to solve then, intuitively, ...
280 views

### Does requiring uniqueness of valid answers for Merlin limit the power of Arthur-Merlin protocols?

Preamble. The complexity class AM are those problems which can be solved by a two-round interactive proof system between a prover "Merlin" and a verifier "Arthur". A problem — which tests some ...
73 views

### how is time complexity defined in computational learning theory

In general, when we say an algorithm $A$ PAC learns $C$ in time $t$, we say $A$ takes time $t$ before outputting a hypothesis $h$, and the hypothesis can be evaluated (on every $x$) in time $t$. Now ...
114 views

### Can we define a meaningful concept of exptime reductions (as opposed to polytime reductions) for classes like NEXP or NEEXP?

Typically we are only interested in polytime reductions as we are usually interested in showing a reduction from one NP-problem to another. However, if we consider larger complexity classes such as ...
99 views

1k views

### Functions that are Not Efficiently Computable but Learnable

We know that (see, e.g., Theorems 1 and 3 of [1]), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable"...
107 views

### When is a problem specified on a TM contained in non-uniform classes such as P/poly? [closed]

In this paper by Gottesman and Irani: https://arxiv.org/abs/0905.2419 , they prove NEXP-hardness of tiling an $N\times N$ grid. They do so by encoding a TM in the tiles making up the grid. However, ...
72 views

254 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 ...
106 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 ...
164 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 ...
133 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
83 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 ...
69 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?
78 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 : ...
55 views

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 $... 1answer 169 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}$... 0answers 451 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,$\...
In an application I'm considering, I need to know the communication complexity of the following problem: Given $n$, let $S$ be the set of integers from $1$ to $n$. Alice, Bob, and Carol each ...