In my view, the formal solution ``P vs NP'' is found in the narrow sense.
http://thescipub.com/pdf/10.3844/jcssp.2012.1036.1040
Also see http://www.bapress.ca/ccc/ccc2013-1/2_13051501_Paper_Plotnikov.pdf
I don't think so. Whatever clever paper you may have written, the current millennium has just started...
I could not find any proper proof of your claims in your paper. How can a paper without any proper proofs, prove anything? Your "proofs" contains undefined terms including terms like "one cycle of the machine", "we believe", "problems without foresight" and "some intermediate results". It looks as the journal has published the paper without proper review.
There is a connected article in http://www.bapress.ca/ccc/ccc2013-1/2_13051501_Paper_Plotnikov.pdf
Dear Dr. Riis,
Do you not like my terminology? Can you write something essentially. Sincerely, AP.
Dr. Plotnikov,
I do not have much experience in theory, so I apologize in advance if my question comes out as naiive. In your opinion, what would be the practical implications of finding such proof? Finding such proof would not make NP problems any easier to solve.
Mr. Garcia,
The first important practical consequence of the results - a statement of the existence of one-way functions, which is of some importance in cryptology. It is indicated the direction of constructing such functions. The second consequence allows developers of the algorithms exclude attempts to seek polynomial-time algorithms for problems outside of the class UF.
You are writing: "We see that such practical
important problems as the Hamiltonian cycle
problem (in the current formulation) cannot
be solved effectively."
The common notion is: we don't know whether
there is a fast characterization of graphs,
whether they contain a Hamiltonian cycle.
Maybe there is a wise hermit in a Tibetan cave
who has found a way to find detected them
in PTIME, but we don't know.
Regards,
Joachim
Dear Dr. Breuer,
As mathematician to mathematician, I shall help you to understand my definition correctly.
> The same paragraph has hopelessly confused English "Let a problem Z, belonging to the class NP, is given to a hereditary system. ", which means nothing in English.
Let R={1,2,3,4} and Q={\oslash, {1},{2},{3},{4},{1,2},{1,3},{2,3}, {3,4},{1,2,3}}. Then (R,Q) is a hereditary system (or a system independence). For example, if {2,3}\in Q and {3}\subset {2,3} then {3}\in Q. I think, definition of hereditary system is given in the paper correctly. This notion can introduce into English language. :)
Also, see http://en.wikipedia.org/wiki/Independence_system
Dear Dr. Breuer,
I can not have alternative point of view to the effect I should write an article in English. I agree with your reasoning on the presentation of the material. The main thing, I hope you have understood the contents of article ("it does not wreck the understandability of the sentence.").
One day, I had a conversation with an English writer. When I apologized for my imperfect English, he said that I am in a better position, because I know the Russian language and understandable English. And he knows only English.
Dear Dr. Breuer,
I am very grateful to you for your remarks. You would be great editor of my paper!
>Try telling in your own words here what you did, please!
OK.
My aim is to show that there exist a class of problems in NP, an intermediate between P and NP. Such a result can be obtained if we consider the process of constructing a solution of the problem of NP in dynamics.
To this end, we are building a set-theoretic model of a problem from NP and show that its solution consists of separate elements of a finite set (literals, vertices or edges of a graph, etc.). Therefore, one way of constructing solutions consists in the fact that we must successively (step by step) find these elements of the solution. In general, one-step of the solution process is that we have selected a few elements of the solution (have intermediate solution) and we must select a new element of the solution. This is the central point!
We need that the new collection of selected elements would be a part of a feasible solution of the problem. In other words, we need to verify the new intermediate solution obtained by joining the next element of the solution (literal, vertex, etc.). Verification consume the time. If we can perform such verification in the polynomial time on the dimension of the problem, then this type of problem belongs to a new class UF. If such verification requires exponential time on the dimension of the problem, then this type of problem belongs to the class NP\UF.
Since P\subset UF and UF\not= NP, we have P\not= NP.
We called a problem of the class UF as a problem without foresight. It is a result of a review of one of the discrete problem. It was necessary to build the edges of alternating circuit or cycle. Each selection of the next edge could be performed correctly if one can foresight subsequent elections edges.
I hope I'm clear stated my thoughts.
> If we can perform such verification
> in the polynomial time on the dimension of
> the problem, then this type of problem
> belongs to a new class UF.
Should read "...belongs to P".
Let's consider Hamiltonian circles. |V| is the
number of vertices, |E| the number of edges.
In the first step one would determine the first
edge systematically. This would cost |E| * p(|E|).
The first factor is for guessing, and p is a
polynomial. One could define p'(|E|) = |E|*p(|E|).
For the next edge you would have the same
costs, the the same costs for the next edge
and so on until you have a Hamilton cycle.
The costs are then O(|E|*p'(E)).
Regards,
Joachim
Dear Joachim Pimiskern,
You claim that you can find the first edge of Hamiltonian circle in |E| * p(|E|), that is, in the polynomial time. Is it correct?
Dear Dr. Breuer,
I think you're talking me how could you wrote this article yourself. You understand all that I have written. Consider my text as my style. I am interested importantly, in your comments there is no answer to my question. Please!
Dear A. Plotnikov,
>You claim that you can find the first edge
> of Hamiltonian circle in |E| * p(|E|),
> that is, in the polynomial time.
not unconditionally. I claim that under the condition that
we had a PTIME verification function
you characterized so:
"If we can perform such verification in the
polynomial time on the dimension of the problem,
then this type of problem belongs to a new
class UF. "
But then it wouldn't be necessary to introduce
UF; Hamilton cycle would be in P.
Regards,
Joachim
Dear Dr. Breuer,
You wrote:
>You now do need to check through it and say whether you agree or disagree with each transliterated sentence in turn.
We will end up with something we can all understand as what you have done.
All right. I'm going to try.
>I understand that you want P ..."I shall represent it concretely in ZF set theory"...
Yes.
>This seems to say "I will define precisely what is meant by 'a solution' in this setting".
From the paper: "Then, each of the subsets of R_j \in Q (j=1,2,...,m) is called an admissible solution of the problem Z and every maximal respect to
inclusion R_j is called support solution of the problem. In the problem Z it is required to find a support solution that satisfies the given conditions."
By the way, that is better: "admissible solution" or "feasible solution"? My dictionary say that "feasible solution".
>I think you mean "I assume that the solution is constructed iteratively in a manner that I will set out".
I can agree.
>...it seems to me that this is (a) quite hypothetical or abstract, with nothing particular or concrete about it,
But mathematics is precisely the abstract science...
>...(b) a model of the general way in which the NP problems we know about are solved in practice, nothing more.
And what else?
Thank you.
Dear Dr.
>The real problem is your use of the words "support solution", which connote nothing to me. Do you mean just "solution"? What's the idea here?
Let the graph is given by the edge list: {{1,2}, {2,3}, {2,4}, {3,4}}. In the graph, we want find the maximum independent set of vertices.Then we have the problem (R, Q), where R = {1,2,3,4}, Q = {{1}, {2}, {3}, {4}, {1,3}, {1, 4}}. All the elements of Q are admissible solutions, and solutions {2}, {1,3}, {1,4} are support ones (according to my definition).
>A) Why do you think that UF is not P, if you do think so?
By the definition of UF, for any problem in this class there exists a polynomial-time solution algorithm. I tried to find the algorithm for one of NP-complete problem (see my paper "Experimental Algorithm for the Maximum Independent Set Problem", Cybernetics and Systems Analysis, 48(5): 41-48).
>>B) Why do you think that UF is not NP?
I think that UF NP, since the set NP\UF consists of problems in which the the verification time of intermediate (not support) solutions is exponential on the dimension of the problem.
The first time I met such problem when in a directed graph, whose vertices are divided into disjoint chains, it was necessary to find an alternating chain (cycle) to move to the new partition with new properties. This problem is described in my works. In the new work (see my paper "On the Structure of the Class NP", Computer Communication & Collaboration, vol.1, issue 1, 2013, 19-23) I have given the example of problem from the set NP\UF.
Dear Dr. Breuer,
>What does "independent" mean here? You must say.
Here as in graph theory: the set of vertices is independent if they are pairwise not adjacent.
>At any rate, your Q is is the set of nonempty subsets of {1,3} or {1,4}.
And {2}.
>Why and how did you choose those? Please provide motivation and rationale.
Here, Q is the set of all independent vertices of the given graph.
>You don't know that that set is nonempty.
For example:
{\bf Heavy tuple (HT)}
{\it Condition}. We are given a finite set $X=\{x_1, x_2, \ldots, x_n\}$ of Boolean variables, a bent-function $f(x_1, x_2, \ldots, x_n)\in \{0, 1\}$, the function $w(x_1, x_2, \ldots, x_n)$ $\in Z^{+}$ and the boundary $E\in Z^{+}$ that can be represented by a finite number $m$ of symbols, where $m$ is a polynomial function of $n$: $m=\omega(n)$. The functions $f(X)$, $w(X)$ are computed in the polynomial time and the function $w(X)$ is not a constant.
{\it Question}. Is there a set of values of Boolean variables $X$ such that $f(X)=1$ and the value of $w(X)$ is at least $E$?
\begin{lemma}
The HT problem belongs to the class NP.
\end{lemma}
{\bf Proof}. Indeed, the initial data of the HT problem and the solution are finite, and the solution has linear dimension of the problem dimension. In addition, the obtained tuple (solution) may be verified in the polynomial time. Therefore $HT\in NP$.\hfill Q.E.D.
\begin{lemma}
\label{tmain}
The HT problem can not be solved in a polynomial time.
\end{lemma}
{\bf Proof}. In the HT problem, there is an implicit requirement to consider all tuples on which the bent-function $f(X)$ equals to 1. It follows of a fact that finding a tuple of maximum weight can only if we consider all the elements of an array of such tuples. Since one of the properties of a bent-function is that exactly on a half of the tuples $X$ its value equal to 1, and on the other half of tuples equal to 0, the verification of the intermediate results is possible only after considering the weights of all tuples on which $f(X)=1$. Since the number of such tuples is equal to $2^{n-1}$, from here it follows the validity of the above statement. \hfill Q.E.D.
>So, what's a "support solution"?
In the set Q, all the maximal independent sets is the support solutions of the problem. Note, the maximum independent set is maximal but the maximal independent set can be not maximum.
>That's an "antichain". Check wikipedia: http://en.wikipedia.org/wiki/Antichain. "an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable".
The concept "antichain" is used in a poset. This is analogue of an independent set in undirected graph.
>What do you mean by a "bent-function"? You surely can't mean a "Bent function", which is a cryptographic thing? That is to say, a boolean function with Walsh transform that is a constant. Why would you want to think about this? [the Walsh transform is the function sum_x (-1)^(f(x)+x.y) of the boolean vector y]
We can use "a balanced function" instead "a bent-function".
>What do you mean by "that"? What are you referring to? The function w? The function f? The bound E? What do you mean by "represented by"?
The bound E.
>So why do you think that is not in P?
In the worst case, to find w(X)
>I did ask you what the output representation for w was, but I never had an answer.
The function w(X) is map: {0;1}^n -> Z^{+}. I think it is clear from context.
>we only _know_ it is an NP-complete problem in general.
We do not know.
>boolean function g(X) == X1&(w(X)
In our opinion, the notion of nondeterminism has disappeared from the current definition of NP, which has led to ambiguities in understanding NP, and caused fundamental difficulties in studying the relation P versus NP.
Here are the two papers that resume the first step of our work :
- What is Cook's theorem?
- What is NP? - Interpretation of a Chinese paradox "white horse is not horse"
Article What is Cook's theorem?
Article What is NP? - Interpretation of a Chinese paradox "white hor...
The class NP is the set of problems, the solution each of which can be verified in polynomial time on the dimension of the problem. And that's that. The rest - the interpretation of this concept. Including non-determinism.
From this concept, it follows that:
a) the problem can be defined by a finite number n of symbols;
b) the problem solution can be represented by a finite number m of symbols,
where m is a polynomial function of n: m = f(n);
c) the time t for verifying the obtained solution is some
polynomial functions of n: t = \varphi(n).
From my point of view, this definition of the class NP is more convenient.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs