Unanswered Questions
292 questions with no upvoted or accepted answers
40
votes
1
answer
844
views
Finding an $st$-path in a planar graph which is adjacent to the fewest number of faces
I am curious whether the following problems has been studied before, but wasn't able to find any papers about it:
Given a planar graph $G$, and two vertices $s$ and $t$, find an
$s$-$t$ path $P$ ...
CommunityBot
- 1
19
votes
0
answers
363
views
Using logic to prove non-regularity of a language
A language $L$ is regular if and only if it is definiable by a sentence in monadic second order logic (MSO) over strings (J.R. Buchi, Weak second-order arithmetic and Finite automata; Z. Math. Logik ...
- 73.1k
9
votes
0
answers
228
views
How to solve the loan graph problem
The problem
A loan graph is a directed weighted graph $\mathcal{G} = (V, A),$ where $A \subseteq V \times V.$ If we have a directed arc $(u, v)$, we interpret it as the node $u$ gave a loan of $w(u, ...
- 52
9
votes
0
answers
99
views
Interval density of time bounded Kolmogorov complexity
The Kolmogorov complexity of a string $x$ is the size of the smallest Turing machine $M$ that started on empty tape produces $x$. To make it computable, we can add a bound on the time used by $M$ to ...
- 82.4k
9
votes
1
answer
853
views
Turing Machine-Like Formalism for The Actor Model
Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done.
The Actor Model is sometimes mentioned as a more powerful computational-...
CommunityBot
- 1
8
votes
0
answers
117
views
Data Structures for Non-Orientable Manifolds
I am looking for a data structure to represent non-orientable manifolds (i.e. meshes like Moebius Strip, but without self-intersection). I will then implement other algorithms using this DS such as, ...
- 73.1k
8
votes
0
answers
94
views
Connections between circuit complexity and Unique Games Conjecture?
Circuit complexity has connections to many questions in complexity theory.
For a couple examples, Ryan Williams shared some in a recent talk and Section 3 of these notes gives simple relations to $\...
- 286
8
votes
0
answers
329
views
What are methods for showing that concurrent objects are not linearizable?
Linearizability is a well-known correctness condition for concurrent objects. It provides the illusion that each operation applied by concurrent processes takes effect instantaneously at some point ...
- 73.1k
8
votes
0
answers
258
views
Complexity of computer algebra for systems of trigonometric equations
As discussed in this question, I drafted a spec algorithm that hinges on finding a specific root of a system of trigonometric equations satisfying the following recurrence:
$\qquad f_{p_0} = 0\\
\...
CommunityBot
- 1
8
votes
2
answers
343
views
Maximum set cover with non-overlap
Let the universe be the set $U$ and a set of subsets $S$ be such that $\cup_{s \in S} s = U$. I am interested in computing the longest sequence of sets $s_1, ..., s_k$ such that:
$s_i \in S$ $\forall ...
- 7,603
7
votes
0
answers
353
views
What was the first public reference to bloom filters where the number of hash functions vary?
In traditional bloom filters, each item is hashed some fixed number of locations. One variant of this is to hash items a varying number of locations within the same bloom filter.
This idea is ...
- 529
7
votes
0
answers
141
views
Evolutionary theory applied to programming languages
I'm looking for books applying evolutionary theory to the history of programming languages. Researching the topic I have found an interesting paper - Modelling the Evolution of Programming Languages ...
7
votes
1
answer
664
views
Using the Chomsky-Schutzenberger theorem to prove a language is not context-free?
The Chomsky-Schutzenberger representation theorem states that a language $L$ is context-free iff there is a homomorphism $h$, a regular language $R$, and a paired alphabet $\Sigma = T \cup \overline{T}...
CommunityBot
- 1
6
votes
0
answers
52
views
How to find the minimum number of elements to distinguish several given sets?
Given $n$ distinct sets $S_1, S_2, \cdots, S_n$, how to find a set $X$ such that $X \cap S_1, X \cap S_2, \cdots, X \cap S_n$ are still distinct, and the size of $X$ is minimum?
For example, given $\{...
- 39.2k
6
votes
0
answers
281
views
Time complexity of linear programming with small number of variables
I have a linear program with $n$ variables, $m$ constraints and $O(nm)$ bit total length (the constraint matrix contains only zeros and ones). I am interested in finding a polynomial time algorithm ...
- 1,339