Re: Hamiltonian cycle problem in 2-connected bipartite cubic graph is Polynomial

On 1月21日, 上午6时47分, jas...@xxxxxxxxxxxxxxxx wrote:
On Jan 16, 6:54 pm, Zhu Guohun <ccgh...@xxxxxxxxxxxxxxxxxxxx> wrote:





On 1月16日, 下午7时33分, Ben Bacarisse <ben.use....@xxxxxxxxx> wrote:

Sorry! The arXiv admin remove my submission, they asked me to improve
my paper quality.

I prove that at least two simplifiedNP-Completeproblems is
polynomial in my paper.
First problem is $(2,3)-SAT$ problem wich is proved NP-Completed by
Raman [1].
Second problem is mimimum vertex cover on bridgeless cubic graph [2].

Now I give some idea of my paper under here.

1. Given a bridgeless cubic graph $G$ and a perfect matching $M$,
if all simple cycles in $G \setminus M$ is minimum,
then the minimum size of vertex cover $vc(G)$ is sum of all minimum
vertex cover of all minimum simple cycle.

2. The complexity of determining minimum odd simple cycle from a
cubic graph is $O(n^4)$.

3. The complexity of determining the minimum vertex cover of a 2-
connected cubic graph is $O(n^4)$.

4. Given a $(2,3)-SAT$ with symmetric Horn formulas, finding
maximum SAT is equal to
fiding a minimum vertex cover of SAT2G mapping graph $G$m, where
$d(G)<=2$

5. Given a $(2,3)-SAT$, the MAX2SAT problem could be determining in
polynomial.

6. Given a $(2,4)-SAT$, the MAX2SAT problem could be determining in
polynomial.

some definition is follows:
7. SAT2G mapping graph: a undirected graph was mapped from 2SAT,
clause --> edge and literal-->vertex

8. Horn formulas: a conjunction formulas which contains at most one
positive literal

9. symmetric Horn formulas: positive monotone formulas \cup Horn
formulas,
for example : $L=(x_1 \vee x_2),(x_2 \vee x_3),(\overline{x_3}
\vee x_1),(\overline{x_1} \vee x_4),(\overline{x_2} \vee
x_5),(\overline{x_3} \vee x_6), (\overline{x_4} \vee \overline{x_5}) ,
( \overline{x_5} \vee \overline{x_6}), ( \overline{x_4} \vee
\overline{x_6})$
where $L$ presents a symmetric Horn $(2,3)-SAT$ formula.

reference
[1]Venkatesh Raman, Bala Ravikumar, S. Srinivasa Rao: A SimplifiedNP-CompleteMAXSAT Problem. Inf. Process. Lett. 65(1): 1-6 (1998)
[2]Paola Alimonti and Viggo Kann. Hardness of approximating problems
on cubic graphs. CIAC 97, 288-298, volume 1203 of LNCS, 1997.
[3]Uehara, R. (1996 ),NP-completeproblems on a 3-connected cubic
planar graph and their applications, 'Technical Report TWCU-M-0004',
Tokyo Woman's Christian University.

----------------------------------
Guohun zhu

Guohun ,
You are wasting your time and others time in writing papers that one
can not even read/understand what any sentence is trying to say.
Your thinking is very immature. If such simple minded ideas could have
worked then this problem would have been solved long long back.
So stop wasting others time and creating more noise in a group like
comp.theory.

-Javaid- 隐藏被引用文字 -

- 显示引用的文字 -

Hi, Javaid,

It is not fair that you think my sentences being nose in group,
because there exists many issue of P vs NP problem in this group or
sci.math, some sentences are more simple than my comments.

I could not understand why you said my sentences on google wasting
your time ! Firstly, you don't show your question of my draft or
coding on this group which could not prove that you have been read my
draft; Secondly, any question of my draft or my coding I always
answer, no matter my draft or others related problem.

Maybe my poor English have wast your time, if it is, I am very sorry,
I will improve my English skills in future.
-----------------------------------------------------------------
Guohun
.

Relevant Pages