Most Popular
1500 questions
15
votes
1 answer
Is MALL + unrestricted recursive types Turing-complete?
If you look at the recursive combinators in the untyped lambda-calculus, such as the Y combinator or the omega combinator:
$$
\begin{array}{lcl}
\omega & = & (\lambda x.\,x\;x)\;(\lambda x.\,x\;x)\\
Y & = & \lambda f.\,(\lambda x.\,f\;(x\;x))\;…
Neel Krishnaswami
- 32,528
- 1
- 100
- 165
15
votes
2 answers
Barriers and Monotone Circuit Complexity
Natural proofs is a barrier towards proving lower bounds on the circuit complexity of boolean functions. They do not directly imply any such barrier in proving lower bounds on the $monotone$ circuit complexity. Is there any progress towards…
Shiva Kintali
- 10,578
- 41
- 74
15
votes
2 answers
What is a zipper, and how does it relate to a tree-like structure?
I was reading a chapter in LYAH which didn't really make sense to me. I understand that zippers can arbitrarily traverse a tree-like structure, but I need some clarification on it. Also, can zippers be generalized to any data structure?
n_ary_crazy
- 151
- 1
- 3
15
votes
3 answers
Combinatorial characterization of exact learning with membership queries
Edit: Since I haven't received any responses/comments in a week, I'd like to add that I'm happy to hear anything about the problem. I don't work in the area, so even if it's a simple observation, I may not know it. Even a comment like "I work in the…
Robin Kothari
- 13,617
- 2
- 60
- 116
15
votes
10 answers
Intractability of NP-complete problems as a principle of physics?
I'm always intrigued by the lack of numerical evidence from experimental mathematics for or against the P vs NP question. While the Riemann Hypothesis has some supporting evidence from numerical verification, I'm not aware of similar evidence for…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149
15
votes
4 answers
Forcing method used in Baker-Gill-Solovay Relativization paper and Cohen's Proof of Continuum Hypothesis Independence
I am generally interested in the forcing method used by Baker-Gill-Solovay and Cohen. I am looking for as many sources as I can get my hands on concerning either the technique itself or its use. Does anyone have suggestions?
djkern
- 533
- 3
- 8
15
votes
0 answers
Semiprime factorization, Groebner bases and a Nullstellensatz certificate
Suppose we have $N=pq$, with $p$ and $q$ are unknown odd primes. We can encode factorization problem in the system of polynomial equations. For instance, $p= 1+ \sum_{k=1}^n 2^k x_k$, $q= 1+ \sum_{k=1}^n 2^k y_k$, where $n = \lfloor \log_2 N \rfloor…
mkatkov
- 537
- 2
- 12
15
votes
2 answers
Are there intermediate eta theories for the lambda calculus?
There are two main, studied theories of the lambda calculus, the beta theory and its Post-complete extension, the beta-eta theory.
Do these two theories have an in-between, a kind of intermediate eta rule that gives a confluent rewrite theory? Is…
Charles Stewart
- 4,316
- 28
- 45
15
votes
2 answers
Under what circumstances do $O(n^{a + \epsilon})$ algorithms imply $O(n^{a+o(1)})$ algorithms?
Suppose that, for each $\epsilon > 0$, there is an Turing machine $M_{\epsilon}$ that decides a language $L$ in time $O(n^{a + \epsilon})$. Is there a single algorithm deciding $L$ in time $O(n^{a + o(1)})$? (Here, the $o(1)$ term is measured in…
David Harris
- 3,488
- 22
- 24
15
votes
3 answers
Linear time in-place riffle shuffle algorithm
Is there a linear time in-place riffle shuffle algorithm? This is the algorithm that some especially dextrous hands are capable of performing: evenly dividing an even-sized input array, and then interleaving the elements of the two halves.
Mathworld…
Johny
- 153
- 1
- 5
15
votes
9 answers
How to Create Mission Critical Software?
I am self learning formal methods. I heard that formal methods is used (and usually only used) to create mission critical software (such as nuclear reactor controller, aircraft flight controller, space probe controller). That's why I am interested…
fajrian
- 251
- 1
- 4
15
votes
1 answer
What can we prove with infinite graphs that we cannot prove without them?
This is a follow-up question to this one about infinite graphs.
Answers and comments to that question list objects and situations which are naturally modeled by infinite graphs. But there are also numerous theorems about infinite graphs (see chapter…
Gregor
- 541
- 3
- 7
15
votes
1 answer
Is the following problem NP hard?
Consider a collection of sets $F=\{F_1,F_2,\dotsc,F_n\}$ over a base set $U=\{e_1,e_2,\dotsc,e_n\}$ where $|F_i|$ $\ll$ $n$ and $e_i \in F_i$, and let $k$ be a positive integer.
The goal is to find another collection of sets…
Rhein
- 151
- 4
15
votes
1 answer
Characterization of read-once formulae over the full binary basis
Background
A read-once formula over a set of gates (also called a basis) is a formula in which each input variable appears once. Read-once formulas are commonly studied over the De Morgan basis (which has the 2-bit gates AND and OR, and the 1-bit…
Robin Kothari
- 13,617
- 2
- 60
- 116
15
votes
1 answer
How efficient are DPLL-based SAT-solvers on satisfiable instances of PHP?
We know that DPLL based SAT-solvers fail to answer correctly on unsatisfiable instances of $\mathrm{PHP}$ (pigeon hole principle), e.g. on "there is a injective mapping from $n+1$ to $n$":
$$\mathrm{PHP^{n+1}_{n}} := \left(\bigwedge_{i\in[n+1]} \…
Kaveh
- 21,577
- 8
- 82
- 183