The famous 0-1 Knapsack problem is: Given and integers, determine whether or not there are values so that The best known worst-case algorithm runs in time times a polynomial in . Is there an algorithm that runs in time ?
Conjecture Given any complex numbers which are linearly independent over the rational numbers , then the extension field has transcendence degree of at least over .
Conjecture \item If is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. \item If the line graph of a locally finite graph is 4-connected, then is hamiltonian.
Conjecture For all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order .
Conjecture For every rational and every rational , there is no polynomial-time algorithm for the following problem.
Given is a 3SAT (3CNF) formula on variables, for some , and clauses drawn uniformly at random from the set of formulas on variables. Return with probability at least 0.5 (over the instances) that is typical without returning typical for any instance with at least simultaneously satisfiable clauses.
We are given a complete simple undirected weighted graph and its first arbitrary shortest spanning tree . We define the next graph and find on the second arbitrary shortest spanning tree . We continue similarly by finding on , etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let be the graph obtained as union of all disjoint trees.
Question 1. What is the smallest number of disjoint spanning trees creates a graph containing a Hamiltonian path.
Question 2. What is the smallest number of disjoint spanning trees creates a graph containing a shortest Hamiltonian path?
Questions 3 and 4. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?
Conjecture An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. Among all the vertices' trees, the star with vertices has the most endomorphisms, while the path with vertices has the least endomorphisms.
Problem Given two codes , their Tensor Product is the code that consists of the matrices whose rows are codewords of and whose columns are codewords of . The product is said to be robust if whenever a matrix is far from , the rows (columns) of are far from (, respectively).
The problem is to give a characterization of the pairs whose tensor product is robust.
Conjecture Let be the open unit disk in the complex plane and let be open sets such that . Suppose there are injective holomorphic functions such that for the differentials we have on any intersection . Then those differentials glue together to a meromorphic 1-form on .
Conjecture Let be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists such that is an element of at least half the members of .
Conjecture For every , there exists an integer such that if is a digraph whose arcs are colored with colors, then has a set which is the union of stables sets so that every vertex has a monochromatic path to some vertex in .
For a graph , let denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let denote the cardinality of a minimum feedback vertex set (set of vertices so that is acyclic).
Conjecture Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a deterministic Turing machine in polynomial time? That is, does P = BPP?
Problem Ian Agol and Matthias Goerner observed that the 4x5 chessboard complex is the complement of many distinct links in the 3-sphere. Their observation is non-constructive, as it uses the resolution of the Poincare Conjecture. Find specific links that have the 4x5 chessboard complex as their complement.
Conjecture For , let be the statement that given any exact -coloring of the edges of a complete countably infinite graph (that is, a coloring with colors all of which must be used at least once), there exists an exactly -colored countably infinite complete subgraph. Then is true if and only if , , or .
Problem Let be natural numbers with . It follows from the pigeon-hole principle that there exist distinct subsets with . Is it possible to find such a pair in polynomial time?
Conjecture For which values of and are there bi-colored graphs on vertices and different colors with the property that all the monochromatic colorings have unit weight, and every other coloring cancels out?
login/create account
and 
integers, determine whether or not there are 
values 
so that 
The best known worst-case algorithm runs in time 
times a polynomial in 
. Is there an algorithm that runs in time 
?![\[ F_n = 2^{2^{n } } + 1 \]](/files/tex/70ca73d7e82af2fee084a8417e172c58cf78b376.png)
Square-Free?
which are linearly independent over the rational numbers 
, then the extension field 
has transcendence degree of at least 
be a prime natural number. Find all primes 
, such that 
.
, for 
if each of the color classes is of size of either 
or 
? 
is a 4-edge-connected locally finite graph, then its 
of a locally finite graph 
there is an integer 
such that every digraph of minimum outdegree at least 
and every rational 
, there is no polynomial-time algorithm for the following problem.
on 
clauses drawn uniformly at random from the set of formulas on 
simultaneously satisfiable clauses. 
and its first arbitrary shortest spanning tree 
. We define the next graph 
and find on 
the second arbitrary shortest spanning tree 
. We continue similarly by finding 
on 
, etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let 
be the graph obtained as union of all 
containing a Hamiltonian path.
is 2-large, then 
, their Tensor Product 
is the code that consists of the matrices whose rows are codewords of 
and whose columns are codewords of 
. The product 
is far from 
be the open unit disk in the complex plane and let 
be open sets such that 
. Suppose there are injective holomorphic functions 
such that for the differentials we have 
on any intersection 
. Then those differentials glue together to a meromorphic 1-form on 
be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists 
such that 
set which is the union of 
, what is the smallest integer 
such that 
? 
denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let 
denote the cardinality of a minimum feedback vertex set (set of vertices 
so that 
is acyclic). 
. 
is for every sets 
and 
has a cycle with length at most 
has a complete graph on 
vertices as a minor. 
, let 
be the statement that given any exact 
-coloring of the edges of a complete countably infinite graph (that is, a coloring with 
-colored countably infinite complete subgraph. Then 
, 
, or 
. 
to be the maximum degree, 
to be the size of the largest 
to be the chromatic number of 
for every graph 
be natural numbers with 
. It follows from the pigeon-hole principle that there exist distinct subsets 
with 
. Is it possible to find such a pair 
in polynomial time? 
has equivalence covering number 
. 
are there bi-colored graphs on 
in 
such that the fundamental group of the complement has an unsolvable word problem? 
, and let ![\[ {\mathbb P}(e \in F \mid f \in F}) \le {\mathbb P}(e \in F) \]](/files/tex/1fe7ac9c579238670e3aa16ae401e8194e1c3da3.png)
Drupal
CSI of Charles University