Sat, 03/06/2010 - 01:36 — manu

Title | Decision P systems and the P≠NP conjecture |

Publication Type | Journal Papers |

Year of Publication | 2003 |

Authors | Pérez-Jiménez, M. J., Romero-Jiménez Á., & Sancho-Caparrini F. |

Journal Title | Lecture Notes in Computer Science |

ISBN Number | 978-3-540-00611-4 |

Publisher | Springer |

Place Published | Amsterdam, The Netherlands |

Volume | 2597 |

Pages | 388-399 |

Abstract | We introduce decision P systems,which are a class of P systems with symbol-objects and external output. The main result of the paper is the following:if there exists an NP-complete problem that cannot be solved in polynomial time,with respect to the input length,by a deterministic decision P system constructed in polynomial time,then P≠NP. From Zandron-Ferreti-Mauri’s theorem it follows that if P≠ NP,then no NP-complete problem can be solved in polynomial time, with respect to the input length,by a deterministic P system with active membranes but without membrane division,constructed in polynomial time from the input. Together,these results give a characterization of P≠NP in terms of deterministic P systems. |

URL | http://dx.doi.org/10.1007/3-540-36490-0_27 |

ISSN Number | 0302-9743 |

DOI | 10.1007/3-540-36490-0_27 |