Conjecture Is the approximation ratio for the Maximum Edge Disjoint Paths (MaxEDP) or the Maximum Integer Multiflow problem (MaxIMF) bounded by a constant in -outerplanar graphs or tree-width graphs?
The zeroes of the Riemann zeta function that are inside the Critical Strip (i.e. the vertical strip of the complex plane where the real part of the complex variable is in ]0;1[), are actually located on the Critical line ( the vertical line of the complex plane with real part equal to 1/2)
Problem Does there exist a polynomial time algorithm which takes as input a graph and for every vertex a subset of , and decides if there exists a partition of into so that only if and so that are independent, is a clique, and there are no edges between and ?
Basic Question: Given any positive integer n, can any convex polygon be partitioned into n convex pieces so that all pieces have the same area and same perimeter?
Definitions: Define a Fair Partition of a polygon as a partition of it into a finite number of pieces so that every piece has both the same area and the same perimeter. Further, if all the resulting pieces are convex, call it a Convex Fair Partition.
Questions: 1. (Rephrasing the above 'basic' question) Given any positive integer n, can any convex polygon be convex fair partitioned into n pieces?
2. If the answer to the above is "Not always'', how does one decide the possibility of such a partition for a given convex polygon and a given n? And if fair convex partition is allowed by a specific convex polygon for a give n, how does one find the optimal convex fair partition that minimizes the total length of the cut segments?
3. Finally, what could one say about higher dimensional analogs of this question?
Conjecture: The authors tend to believe that the answer to the above 'basic' question is "yes". In other words they guess: Every convex polygon allows a convex fair partition into n pieces for any n
Setup Fix a tree and for every vertex a non-negative integer which we think of as the amount of gold at .
2-Player game Players alternate turns. On each turn, a player chooses a leaf vertex of the tree, takes the gold at this vertex, and then deletes . The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.
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?
login/create account
be an integer and let 
be a minor minimal 
. Then either 
minor for some 
or 
is an invertible 
matrix, then there is an 
of ![$ [A A] $](/files/tex/d1e9d82c656535b507686183e640178057fae455.png)
so that 
is nonzero. 
is a 
-connected planar graph, then 
has a Hamilton cycle. 
be a digraph. If 
, then 
. 
has a homomorphism to 
. 
and a function 
such that if 
, then every saturated 
has cardinality at least 
? 
? 
a subset 
of 
, and decides if there exists a partition of 
into 
so that 
only if 
and so that 
are independent, 
is a clique, and there are no edges between 
and 
? 
edges whose deletion destroys every odd cycle. 
and for every vertex 
a non-negative integer 
which we think of as the amount of gold at 
. 
, every (loopless) graph 
immerses 
. 
, there is an integer 
so that every strongly 
is prime and 
, we write 
if 
satisfies 
. The problem of finding such an integer 
for a given 
(with 
) is the Discrete Log Problem.
Drupal
CSI of Charles University