On a Paun's Conjecture in Membrane Systems

Description

We study a P˘aun's conjecture concerning the unsolvability of NP–complete problems by polarizationless P systems with active membranes in the usual framework, without cooperation, without priorities, without changing labels, using evolution, communication, dissolution and division rules, and working in maximal parallel manner. We also analyse a version of this conjecture where we consider polarizationless P systems working in the minimally parallel manner.

Abstract

Ministerio de Educación y Ciencia TIN2006–13425

Abstract

Junta de Andalucía TIC–581

Additional details