# All Questions

9,933 questions
7 views

### Prove A ⋄ B := {xy|x ∈ A, y ∈ B, |x| = |y|} is context-free without using PDA [on hold]

For any regular languages A, B, A ⋄ B := {xy|x ∈ A, y ∈ B, |x| = |y|}. Prove that A ⋄ B is context-free. So far: I know how to show that the reverse of L is regular. And then I need to build a CFG ...
9 views

### If f(n) is Big Theta of g(n), then are they also both lower bounds of each other? [on hold]

Is it necessarily true that if: $f(n) = \Theta(g(n))$ Then $f(n) = \Omega(g(n))$ and $g(n) = \Omega(f(n))$
16 views

24 views

### Is nand a counterexample to Lawvere’s fixed point theorem for the 2 point set?

To quote Lawvere (Conceptual Mathematics, p. 305) “Applying Cantor's Theorem we can conclude that no map T x T —>2 can parameterize all maps T —>2.” But nand would seem to be such a map. It maps 2 x 2 ...
19 views

### How to prove Euler formula for graph theory? [on hold]

How to prove Euler formula for hypergraph? How we defines faces in hyper graphs ?
32 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 ...
29 views

51 views

### Are there experiments in artificial life on the emergence of sexual reproduction (analogues)?

I'm aware of quite a few experiments on the emergence of replicators in various artificial life areas, e.g. from cellular automata to computer programs. Have any similar result been obtained on the ...
47 views

### Confusion about the visibility and arbitration relations in a formal framework for distributed consistency models

In the POPL'14 paper "Replicated Data Types: Specification, Verification, Optimality" and the book "Principles of Eventual Consistency", the authors propose a formal framework for specifying ...
68 views

### The SQ argument in Balazs Szorenyi's paper

I am asking about the proof in Theorem 5 (page 6) of this paper, http://www.inf.u-szeged.hu/~szorenyi/Cikkek/sq_d0_ext.pdf Quite a few things about this short argument seem unclear to me, Towards ...
41 views

### Counting sum of parities of cycle covers in cubic, planar, bipartite graphs

Let $G$ be a cubic (i.e. every degree exactly three), planar, bipartite graph. By Hall's theorem its edges can be partitioned into three perfect matchings. Take any such partition $M_0,M_1,M_2$ and ...
70 views

### Is there a universal gate set for classical probabilistic computing?

We know that NAND gates are universal for deterministic classical circuits, Toffoli gates are universal for reversible deterministic classical circuits, and Clifford+T is universal for quantum ...
97 views

### Optimal bounds for $k$-wise non-uniform random bits

Let $k\geq 2$ be a constant (in my case, $k=4$), and $n,t \geq 0$ be integers such that $2^t \leq n$. What is the smallest sample space (or, equivalent, how many true independent random bits are ...
129 views

### Take a NEXP-complete problem and then have the input in unary. Why is this not NP-complete?

It is known that if any unary language is NP-complete, then P=NP. Suppose we take a NEXP-complete language with input $x$ in binary and witness $y\in\{0,1\}^{2^{poly(|x|)}}$ such that the verifying ...
175 views

### Subset sum problem with at most one solution for any target

This question was originally asked on CS.se. A little bit of initial discussion can be found in the comments there. We first consider the search version of the subset sum problem: Given a set $S$ of ...
127 views

### Why is the Toffoli Gate named after Toffoli?

I was reading the following paper: Rolf Landauer, Irreversibility and Heat Generation in the Computing Process, IBM Journal of Research and Development, Volume 5, Issue 3, July 1961. On page 4, ...
16 views

### Why do functions in Vimscript require a “call” statement? [migrated]

In Vimscript, if you use a function as an R-value, then the function simply evaluates. For example: let count_pattern += str2nr( strpart( execute( command ), 1 ) ) ...
165 views

### $BPP$ before Adleman-Sipser-Gacs theorem?
Where was $BPP$ before it was in second level? If we show $BPP$ is in $P^{NP}$ then we would've separated $BPP$ from $EXP^{NP}$. What did $BPP$ in second level accomplish? Did it have to cross any ...