WordEquationSatisfiability < CoWiki

CoWiki Web>ImportantOpenProblems>WordEquationSatisfiability (2011-08-07, StepanHolub) (raw view)

Is deciding the satis&#64257;ability of word equations in NP? This question is
equivalent to asking whether one can check the correctness of a proposed 
solution of a word equation within a time bound that is polynomial in the size 
(length) of the equation. It is known that solving word equations is NP-hard, and it is known that it is in PSPACE, that is, one can decide the 
question using polynomial space (and exponential time). It is also known 
that, if the size of the shortest solution (if it exists) is exponentially 
bounded by the size of the equation, then solving equations is in NP. 
So far, only a double exponential bound has been shown. 


-- Main.JeffreyShallit - 13 Jul 2011

Topic revision: r2 - 2011-08-07 - StepanHolub

CoWiki

CoWiki Web
CoWiki Web Home
Changes
Index
Search

Webs
- AIMAS
- CERAS
- CF
- CoWiki
- CrySP
- External
- Faqtest
- HCI
- Himrod
- ISG
- Main
- Multicore
- Sandbox
- TWiki
- TestNewSandbox
- TestWebS
- UW

My links
- People
- CERAS
- WatForm
- Tetherless lab
- Ubuntu Main.HowTo
- eDocs
- RGG NE notes
- RGG
- CS infrastructure
- Grad images

Edit