Timeline for Is every input gate of a Boolean Circuit (to decide a language) on a path to the output gate?
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 25, 2010 at 9:12 | vote | accept | Niall Murphy | ||
| May 25, 2010 at 9:11 | comment | added | Niall Murphy | @Ryan You have answered the question. Unfortunately your trick construction isn't applicable for my exact system, I'll have to think of some other way around it. Thanks! | |
| May 24, 2010 at 9:12 | comment | added | Ryan Williams | @Niall: Did you have any further comments on my answer to your question? | |
| May 20, 2010 at 22:25 | history | edited | Ryan Williams | CC BY-SA 2.5 |
added 854 characters in body; deleted 11 characters in body
|
| May 20, 2010 at 22:16 | comment | added | Ryan Williams | @Niall: That sounds like a annoying problem to have. There is a kind of dumb way to enforce the condition that may help you, which I will describe in an update to my answer. | |
| May 20, 2010 at 21:50 | comment | added | Niall Murphy | @Grigory Yes its still NL-complete, you can (in at least logspace) convert a cyclic graph to a leveled acyclic graph (the construction is very similar to the one on page 333 of Sipser's Textbook (2nd edition)). | |
| May 20, 2010 at 21:44 | comment | added | Niall Murphy | I'm looking for a sub LOGSPACE upperbound for a DLOGTIME-uniform family. Algorithms for arbitrary circuits keep hitting (as you mention) s t connectivity or needing transitive closure. I was hopping that I could assume every input gate was on a path to the output to bypass around this problem. | |
| May 20, 2010 at 21:29 | comment | added | Grigory Yaroslavtsev | Boolean circuit is an acyclic graph, are you sure that accessibility problem for acyclic graphs is still $NLOGSPACE$-complete? | |
| May 20, 2010 at 19:50 | history | answered | Ryan Williams | CC BY-SA 2.5 |