On the complexity of intersecting finite state automata and NL versus NP
Φόρτωση...
Ημερομηνία
Συγγραφείς
Karakostas, G.
Lipton, R. J.
Viglas, A.
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
peer reviewed
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Theoretical Computer Science
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
We consider uniform and non-uniform assumptions for the hardness of an explicit problem from finite state automata theory. First we show that a small improvement in the known straightforward algorithm for this problem can be used to design faster algorithms for subset sum and factoring, and improved deterministic simulations for non-deterministic time. On the other hand, we can use the same improved algorithm for our FSA problem to prove complexity class separation results (NL is not equal to P, or NP for the non-uniform case). This result can be viewed either as a hardness result for the FSA intersection problem, or as a method for separating NL from P or NP. It is interesting to note that this approach is based on a more general method for separating two complexity classes, using algorithms rather than lower bounds. (C) 2002 Elsevier Science B.V. All rights reserved.
Περιγραφή
Λέξεις-κλειδιά
complexity class separations, nl, np, finite state automata intersection, space, time
Θεματική κατηγορία
Παραπομπή
Σύνδεσμος
<Go to ISI>://000183608800013
http://ac.els-cdn.com/S0304397502008307/1-s2.0-S0304397502008307-main.pdf?_tid=610c34ee-873f-11e3-8d47-00000aab0f6c&acdnat=1390819383_8cb4ebf5ca7cd5001a8bfc9357c9c764
http://ac.els-cdn.com/S0304397502008307/1-s2.0-S0304397502008307-main.pdf?_tid=610c34ee-873f-11e3-8d47-00000aab0f6c&acdnat=1390819383_8cb4ebf5ca7cd5001a8bfc9357c9c764
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Όνομα επιβλέποντος
Εξεταστική επιτροπή
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών