Questions tagged [open-problem]
Problems without an answer after substantial efforts by many users. This tag indicates the problem is of graduate research level and beyond. Do not use this tag for a homework question. Do not use this tag for a question that do not have a solution that can be proved mathematically.
11
questions
0
votes
2
answers
142
views
( Soft question ) P vs NP - is such a situation possible?
Currently P vs NP is the holy grail of theoretical computer science. And the nature of the problem is as such that if actually P = NP is proved then most of the proofs for mathematical statements ...
1
vote
0
answers
25
views
Determine whether we can pack $(r_1, \dots, r_k)$ copies of the variables $(A_1, \dots, A_k)$ into a string $s$, in time polynomial in $|s|$?
Let $s \in \Sigma^*$ be a finite string over alphabet $\Sigma$. Find all "compressible" substrings of $s$, that is substrings $t \leqslant s$ (notation) such that $t\alpha t \leqslant s$ ...
8
votes
1
answer
740
views
Conjecture: a half of a pairing context-free language must be a regular language
If $A$ and $B$ are languages, let $A\bowtie B$ denote the set of strings made by concatenating any word from $A$ and any word from $B$ of equal length.
$$A\bowtie B \equiv \{ ab : a\in A,\;b\in B, |a|=...
0
votes
1
answer
24
views
Can we simply consider a pseudo random number generator to be a function $f: \Bbb{Z}_n \to \Bbb{Z}_n$ for ever-increasing $n$?
On modern architectures, random number generators get seeded by the current system time as a source of randomness, which is nice because it is kind of unpredictable when a process will switch to the ...
3
votes
1
answer
241
views
Changing a matrix to become an ancestry matrix
An ancestry matrix $M$ for rooted tree $T$ is defined as $M[ij] = 1$ iff node $i$ is an ancestor of node $j$. Suppose we are given a matrix $X$. We can easily check that if $X$ is compatible with some ...
6
votes
2
answers
135
views
Topological sort where some nodes can't come in between two other nodes
I have a DAG which I would like to do a topological sort on but there is a catch. I also have a relation NotBetween(X,Y,Z) which means that in the sort the node Y cant come "in between" node ...
6
votes
1
answer
372
views
Is the buckets of water problem in NP?
Continuing from this question: the buckets of water problem.
(All the definitions can be found there, so I will not repeat them).
As seen there by Yuval's answer, the problem is NP-Hard.
I was ...
1
vote
0
answers
109
views
What are open problems in computer science? [closed]
I should prepare some paper for a colloquium (kinda student-task) and it should cover the following points:
(1) at least one notable discovery in theoretical informatics (or computer science)
(2) at ...
14
votes
2
answers
2k
views
Flow graph that requires pushing back flow in Ford Fulkerson
Does there exist a flow graph that always requires flow to be pushed back no matter what ordering of augmenting paths is chosen in Ford Fulkerson?
Let's assume we use the standard procedure of ...
10
votes
1
answer
4k
views
Worst-case input for median-of-medians with groups of size 3
Typically, median of medians algorithm is written with groups of size $5$ or $7$ to ensure worst-case linear performance. The argument against groups of size $k=3$ is typically that we get a ...
26
votes
3
answers
2k
views
Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?
Is the following language context free?
$$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $$
As pointed out by sdcvvc, a word in this language can also be ...