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.

Filter by
Sorted by
Tagged with
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 ...
Aditya Mishra's user avatar
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$ ...
Daniel Donnelly's user avatar
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|=...
user326210's user avatar
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 ...
Daniel Donnelly's user avatar
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 ...
Dandelion's user avatar
  • 287
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 ...
Isak's user avatar
  • 61
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 ...
Eric_'s user avatar
  • 445
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 ...
Constantin's user avatar
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 ...
ryan's user avatar
  • 4,471
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 ...
ryan's user avatar
  • 4,471
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 ...
Robert777's user avatar
  • 747