There is a Hyper-Greedoid lurking behind every Graphical Accessible Computational Search Problem solvable in Polynomial Time: $P \not= NP$
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2018
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915142342541312 |
|---|---|
| author | Kayibi, Koko-Kalambay Kalafan |
| author_facet | Kayibi, Koko-Kalambay Kalafan |
| contents | Consider $G[X]$, where $G$ is a connected, isthmus-less and labelled graph, and $X$ is the edge-set or the vertex-set of the graph $G$. A Graphical Search Problem (GSP), denoted $Π(G[X],γ)$, consists of finding $Y$, where $Y \subseteq X$ and $Y$ satisfies the predicate $γ$ in $G$. The subset $Y$ is a solution of the problem $Π(G[X],γ)$. A sub-solution of $Π(G[X],γ)$ is a subset $Y'$ such that $Y'$ is not a solution of $Π(G[X],γ)$, but $Y'$ is a solution of the problem $Π(H[X'],γ)$, where $X' \subset X$ and $H[X']$ is a contraction-minor of $G[X]$. Solutions and sub-solutions are the feasible sets of $Π(G[X],γ)$.
Let $\mathfrak{I}$ be the family of all the feasible sets of $Π(G[X],γ)$. A Hyper-greedoid is a set system $(X, \mathfrak{I})$ satisfying the following axioms.
A1: Accessibility: if $I \in \mathfrak{I}$, there is an element $x \in I$ such that $I-x \in \mathfrak{I}$
A2: Augmentability: If $I$ is a sub-solution, there is a polynomial time function $κ: \mathfrak{I} \rightarrow \mathfrak{I}$ and there is a element $x \in X-κ(I)$ such that $κ(I) \cup x \in \mathfrak{I}$. That is, every sub-solution can be augmented using a polynomial time algorithm akin to Edmond Augmenting Path Algorithm.
Given a graph $G$, the GSP MISP consists of finding an independent set of vertices of $G$. MISP satisfies axioms A1 and A2. Using the P-completeness of the Decision Problem associated to MISP, we prove that every GSP that satisfies A1 is solvable in Polynomial Time if and only if it satisfies A2. On the other hand, let HCP be the GSP that consists of finding a Hamiltonian cycle of the graph $G$. HCP satisfies A1, but does not satisfies A2. Since the Decision Problem associated with HCP is NP-Complete, we get $P \not = NP$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1802_03028 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | There is a Hyper-Greedoid lurking behind every Graphical Accessible Computational Search Problem solvable in Polynomial Time: $P \not= NP$ Kayibi, Koko-Kalambay Kalafan Computational Complexity Consider $G[X]$, where $G$ is a connected, isthmus-less and labelled graph, and $X$ is the edge-set or the vertex-set of the graph $G$. A Graphical Search Problem (GSP), denoted $Π(G[X],γ)$, consists of finding $Y$, where $Y \subseteq X$ and $Y$ satisfies the predicate $γ$ in $G$. The subset $Y$ is a solution of the problem $Π(G[X],γ)$. A sub-solution of $Π(G[X],γ)$ is a subset $Y'$ such that $Y'$ is not a solution of $Π(G[X],γ)$, but $Y'$ is a solution of the problem $Π(H[X'],γ)$, where $X' \subset X$ and $H[X']$ is a contraction-minor of $G[X]$. Solutions and sub-solutions are the feasible sets of $Π(G[X],γ)$. Let $\mathfrak{I}$ be the family of all the feasible sets of $Π(G[X],γ)$. A Hyper-greedoid is a set system $(X, \mathfrak{I})$ satisfying the following axioms. A1: Accessibility: if $I \in \mathfrak{I}$, there is an element $x \in I$ such that $I-x \in \mathfrak{I}$ A2: Augmentability: If $I$ is a sub-solution, there is a polynomial time function $κ: \mathfrak{I} \rightarrow \mathfrak{I}$ and there is a element $x \in X-κ(I)$ such that $κ(I) \cup x \in \mathfrak{I}$. That is, every sub-solution can be augmented using a polynomial time algorithm akin to Edmond Augmenting Path Algorithm. Given a graph $G$, the GSP MISP consists of finding an independent set of vertices of $G$. MISP satisfies axioms A1 and A2. Using the P-completeness of the Decision Problem associated to MISP, we prove that every GSP that satisfies A1 is solvable in Polynomial Time if and only if it satisfies A2. On the other hand, let HCP be the GSP that consists of finding a Hamiltonian cycle of the graph $G$. HCP satisfies A1, but does not satisfies A2. Since the Decision Problem associated with HCP is NP-Complete, we get $P \not = NP$. |
| title | There is a Hyper-Greedoid lurking behind every Graphical Accessible Computational Search Problem solvable in Polynomial Time: $P \not= NP$ |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/1802.03028 |