How complex is to solve a hard problem with accepting splicing systems

Mitrana, Victor and Păun, Paul Andrei and Păun, Micaela (2019). How complex is to solve a hard problem with accepting splicing systems. In: "COMPLEXIS 2019", 02/05/2019 - 04/05/2019, Grecia. ISBN 978-989-758-366-7. pp. 27-35. https://doi.org/10.5220/0007715900270035.

Description

Title: How complex is to solve a hard problem with accepting splicing systems
Author/s:
  • Mitrana, Victor
  • Păun, Paul Andrei
  • Păun, Micaela
Item Type: Presentation at Congress or Conference (Article)
Event Title: COMPLEXIS 2019
Event Dates: 02/05/2019 - 04/05/2019
Event Location: Grecia
Title of Book: Proceedings of the 4th International Conference on Complexity, Future Information Systems and Risk
Date: 2019
ISBN: 978-989-758-366-7
Volume: 1
Subjects:
Freetext Keywords: Splicing; Accepting Splicing System; Computational Complexity; Descriptional Complexity; 3-colorability Problem
Faculty: E.T.S.I. de Sistemas Informáticos (UPM)
Department: Sistemas Informáticos
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img] PDF - Users in campus UPM only - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (443kB)

Abstract

We define a variant of accepting splicing system that can be used as a problem solver. A condition for halting the computation on a given input as well as a condition for making a decision as soon as the computation has stopped is considered. An algorithm based on this accepting splicing system that solves a well-known NP-complete problem, namely the 3-colorability problem is presented. We discuss an efficient solution in terms of running time and additional resources (axioms, supplementary symbols, number of splicing rules. More precisely, for a given graph with n vertices and m edges, our solution runs in O(nm) time, and needs O(mn2) other resources. Two variants of this algorithm of a reduced time complexity at an exponential increase of the other resources are finally discussed.

Funding Projects

TypeCodeAcronymLeaderTitle
UnspecifiedPOC P-37-257UnspecifiedRomanian National Authority for Scientific Research and InnovationUnspecified

More information

Item ID: 65195
DC Identifier: https://oa.upm.es/65195/
OAI Identifier: oai:oa.upm.es:65195
DOI: 10.5220/0007715900270035
Official URL: http://www.complexis.org/?y=2019
Deposited by: Memoria Investigacion
Deposited on: 01 Mar 2021 08:56
Last Modified: 01 Mar 2021 08:56
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM