Most Popular
1500 questions
15
votes
1 answer
Why do functional programming languages require garbage collection?
What's stopping ghc from translating Haskell into a concatenative programming language such as combinatory logic and then simply using stack allocation for everything? According to Wikipedia, the translation from lambda calculus to combinatory logic…
Nicholas Grasevski
- 159
- 1
- 4
15
votes
3 answers
Irreducible languages
This is not necessarily a research question. Just a question out of curiosity:
I am trying to understand if one can define "irreducible" languages.
As a first guess I call a language L "reducible" if it can be written as
$L = A \cdot B$ with $A \cap…
user35803
15
votes
3 answers
On the realisation of monoids as syntactic monoids of languages
Let $L \subseteq X^{\ast}$ be some language, then we define the syntactic congruence as
$$
u \sim v :\Leftrightarrow \forall x, y\in X^{\ast} : xuy \in L \leftrightarrow xvy \in L
$$
and the quotient monoid $X^{\ast} / \sim_L$ is called the…
StefanH
- 2,077
- 13
- 21
15
votes
0 answers
Is it NP-hard to find (the root of) a small decision tree for a monotone boolean function?
Last year I spent some time trying to prove or disprove the following:
Conjecture. Consider a graph $G$ and define a 2-DNF formula $\phi$ that contains a term $x \land y$ iff $x\mathrel{-\!-}y$ is an edge of $G$. Now consider a decision tree $T$…
Radu GRIGore
- 4,796
- 30
- 69
15
votes
1 answer
Most significant bit of integer multiplication and binary decision diagrams
Let $x$ and $y$ two binary numbers with $n$ bits and $z = x \cdot y\ $ the binary number (length $2n$) of the product of $x$ and $y$. We want to compute the most siginifcant bit $z_{2n-1}$ of the product $z = z_{2n-1} \ldots z_0$.
In order to…
Marc Bury
- 1,338
- 9
- 17
15
votes
1 answer
How to determine whether a proof requires "higher-order reasoning techniques"?
The question:
Suppose I have a specification of a problem consisting of axioms and a goal (i.e. the associated proof problem is whether the goal is satisfiable given all the axioms). Let us also assume that the problem does not contain any…
Sylvia Grewe
- 159
- 3
15
votes
0 answers
Reference request: a more complete "faster factorization into coprimes"
Some months ago, before the advent of "CS-Theory", I asked a question on MathOverflow about efficiently factoring an integer N into coprime factors n1 and n2, where n1 is a multiple of a given a factor d of N.
One of the answers pointed me to Dan…
Niel de Beaudrap
- 8,821
- 31
- 70
15
votes
0 answers
Complexity of approximating the range of a matrix
Given an $m$ by $n$ matrix $M$ with $m \leq n$ and elements from $\{-1,1\}$, let us define:
$$S_M = |\{Mx : x \in \{-1,1\}^n\}|.$$
I believe that it is NP-hard to compute $S_M$ exactly, by applying the reductions from Decide whether a matrix's…
Simd
- 3,902
- 20
- 49
15
votes
2 answers
Poly time superset of NP complete language with infinitely many strings excluded from it
For any arbitrary NP complete language is there always a polytime superset the complement of which is also infinite?
A trivial version which does not stipulate the superset to have infinite complement has been asked at…
ARi
- 405
- 2
- 8
15
votes
2 answers
Number of mincuts of a graph without using Karger's algorithm
We know that Karger's mincut algorithm can be used to prove (in a non-constructive way) that the maximum number of possible mincuts a graph can have is $n \choose 2$.
I was wondering if we could somehow prove this identity by giving a bijective…
Akash Kumar
- 1,973
- 16
- 27
15
votes
4 answers
Theoretical computer science self-study resources for programmers
I am a pretty proficient software engineer, but
I don't know much theory.
I want to learn more theory.
Particular topics that I am interested in are:
computational complexity, formal languages, and type theory.
But I am at a loss as for how to…
Henry H.
- 153
- 1
- 5
15
votes
1 answer
2FA state complexity of k-Clique?
In simple form:
Can a two-way finite automaton recognize $v$-vertex graphs that contain a triangle with $o(v^3)$ states?
Details
Of interest here are $v$-vertex graphs encoded using a sequence of edges, each edge being a pair of distinct vertices…
András Salamon
- 19,000
- 3
- 64
- 150
15
votes
2 answers
Potentially equal complexity classes without known contradictory relativizations
What are some examples of pairs of complexity classes $A$ and $B$ such that
we do not know whether $A=B$, and
we do not know contradictory relativizations either (i.e., we do not know oracles $P$ and $Q$ such that $A^P = B^P$ and $A^Q \ne…
Timothy Chow
- 7,550
- 35
- 43
15
votes
2 answers
Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
The $k$-cycle problem is as follows:
Instance: An undirected graph $G$ with $n$ vertices and up to $n \choose 2$ edges.
Question: Does there exist a (proper) $k$-cycle in $G$?
Background: For any fixed $k$, we can solve $2k$-cycle in $O(n^2)$…
Michael Wehar
- 5,127
- 1
- 24
- 54
15
votes
1 answer
Logical Reations for an Impredicative System in a Predicative MetaTheory
Logical Relations for Impredicative languages like System F seem to rely critically on impredicativity of the ambient logic. Specifically, the interpretation for the forall-type will be defined in terms of all typed relations. In an impredicative…
Max New
- 1,675
- 9
- 24