
Recent Posts
Archives
Meta
Author Archives: mkatkov
Semiprime factorization and modular arithmetics
Edit 6.6.2016. Premature optimization is a source for errors. The following is completely wrong. Would like to smoke the same thing again. Linear algebra does not work here. We need characterization of quotient space. What I do not understand is … Continue reading
Posted in Uncategorized
1 Comment
Why P could be equal NP
In the previous post we have established relation between P vs NP problem and quartic positive polynomial optimization problem. Here I will give some intuition why it is possible that we would be able to decide that quartic polynomial has … Continue reading
Posted in Uncategorized
Leave a comment
Generating positive polynomials that are not sums of squares
Motivation: “To prove that P=NP”. More seriously, there is a very powerful technique, called Sum of Squares (SOS) of polynomials in the optimization. For instance, if , where and are some polynomials it is obvious that is nonnegative. Unfortunately, this does … Continue reading
Posted in Uncategorized
1 Comment
HilbertRobinsonReznickBlekherman positive polynomials
Reznick (2007) (see previous post) simplified Robinson simplification of Hilbert construction of positive polynomials that are not sums of squares by his perturbation lemma. Blekherman shows that the mystery is in the dimension of monomial basis. For example, there are … Continue reading
Posted in Uncategorized
2 Comments
P vs NP – an analogy between analogies
There are few ingredients that may allow to prove that P=NP, although most people believe in opposite. Here I draw outline. 1. Partition problem: given multiset with entries tell whether it is possible to divide it into two miltisets having … Continue reading
Posted in Uncategorized
Leave a comment
Lonely Runner Conjecture. General case.
We consider (LRC) . Conjecture Suppose runners having distinct constant speeds start at a common point (origin) and run laps on a circular track with circumference 1. Then, there is a time when no runner is closer than from the … Continue reading
Posted in Uncategorized
Leave a comment
On the lonely runner conjecture III
We consider (LRC) . Conjecture Suppose runners having distinct constant integer speeds start at a common point (origin) and run laps on a circular track with circumference 1. Then, there is a time when no runner is closer than from … Continue reading
Posted in Uncategorized
1 Comment
On the lonely runner conjecture II
We consider (LRC) . Conjecture Suppose runners having distinct constant integer speeds start at a common point (origin) and run laps on a circular track with circumference 1. Then, there is a time when no runner is closer than from … Continue reading
Posted in Uncategorized
1 Comment
Cantor diagonal argument is almost surely inconsistent
Here we construct table consisted of realization of Bernoulli processes; using Cantor diagonal argument we construct row that is not in the table, and finally we show that constructed number is almost surely in the table countably infinite number of … Continue reading
Posted in Uncategorized
1 Comment
Nullspace of tautologies
Below is Mathematica printout showing the usefulness of tautologies. tautologies6vars4thOrder Given and equations , one can expact 64 dimensional nullspace in the space of monomials of some degree. The above show that in the usual Nullstellensatz case one need 8th … Continue reading
Posted in Uncategorized
Leave a comment