Unambiguous functions in logarithmic space - CiE 2009
•
0 likes•810 views
This document discusses unambiguous functions in logarithmic space. It introduces a new model for nondeterministic function classes that uses unambiguous machines with deterministic answers and oracle-based input/output. It then defines unambiguous reductions between functions based on uniformly unambiguous input transformations and a function gathering results. As an example, it describes reducing the problem of counting simple paths between nodes in a graph to counting more paths in a restricted class of graphs. The approach relates computational ambiguity to input ambiguity and allows improving some previous results.
Recommended
Recommended
More Related Content
What's hot
What's hot (20)
Viewers also liked
Viewers also liked (18)
Similar to Unambiguous functions in logarithmic space - CiE 2009
Similar to Unambiguous functions in logarithmic space - CiE 2009 (20)
Recently uploaded
Recently uploaded (20)
Unambiguous functions in logarithmic space - CiE 2009
- 1. Unambiguous Functions in Logarithmic Space Grzegorz Herman Michael Soltys Computability in Europe July 21, 2009
- 2. The Context
- 3. The Context nondeterminism for bounded space well understood. . .
- 4. The Context nondeterminism for bounded space well understood. . . except L vs. NL (since 2004, SL vs. NL)
- 5. The Context nondeterminism for bounded space well understood. . . except L vs. NL (since 2004, SL vs. NL) unambiguity seems to be the most useful intermediate step
- 6. The Context nondeterminism for bounded space well understood. . . except L vs. NL (since 2004, SL vs. NL) unambiguity seems to be the most useful intermediate step a breakthrough due to Reinhardt and Allender (1997): UL/poly = NL/poly
- 7. The Context nondeterminism for bounded space well understood. . . except L vs. NL (since 2004, SL vs. NL) unambiguity seems to be the most useful intermediate step a breakthrough due to Reinhardt and Allender (1997): UL/poly = NL/poly no major results since
- 8. Rationale
- 9. Rationale want to measure relative (un)ambiguity of problems
- 10. Rationale want to measure relative (un)ambiguity of problems need a meaningful notion of unambiguous nondeterministic reductions
- 11. Rationale want to measure relative (un)ambiguity of problems need a meaningful notion of unambiguous nondeterministic reductions need a well-behaved model for computing functions
- 12. Nondeterministic Function Classes: Existing Models
- 13. Nondeterministic Function Classes: Existing Models multi-valued functions, or
- 14. Nondeterministic Function Classes: Existing Models multi-valued functions, or functions expressing properties of computation graphs (e.g., #L, GapL), or
- 15. Nondeterministic Function Classes: Existing Models multi-valued functions, or functions expressing properties of computation graphs (e.g., #L, GapL), or deterministic computation with oracle queries (e.g., FNL = FLNL).
- 16. Nondeterministic Function Classes: Our Model
- 17. Nondeterministic Function Classes: Our Model nondeterministic machines with deterministic answers
- 18. Nondeterministic Function Classes: Our Model nondeterministic machines with deterministic answers oracle-based input and output
- 19. Nondeterministic Function Classes: Our Model nondeterministic machines with deterministic answers oracle-based input and output explicit failures (uncatchable exceptions)
- 20. Nondeterministic Function Classes: Our Model nondeterministic machines with deterministic answers oracle-based input and output explicit failures (uncatchable exceptions) (un)ambiguity captured by the shape of computation graphs
- 22. Reductions: The Definition A function φ : A → B reduces to ψ : C → D if there exist:
- 23. Reductions: The Definition A function φ : A → B reduces to ψ : C → D if there exist: uniformly unambiguous, parametrized family of input transformations: θi : A → C, and
- 24. Reductions: The Definition A function φ : A → B reduces to ψ : C → D if there exist: uniformly unambiguous, parametrized family of input transformations: θi : A → C, and a function gathering the results on the transformed inputs: ξ : D∗ → B,
- 25. Reductions: The Definition A function φ : A → B reduces to ψ : C → D if there exist: uniformly unambiguous, parametrized family of input transformations: θi : A → C, and a function gathering the results on the transformed inputs: ξ : D∗ → B, such that ξ(ψ(θ0(x)), . . . , ψ(θp(|x|)(x))) = φ(x)
- 27. Reductions: An Example target problem: counting up to k simple paths between s and t
- 28. Reductions: An Example target problem: counting up to k simple paths between s and t reduced problem: counting up to k + 1 simple paths between s and t
- 29. Reductions: An Example target problem: counting up to k simple paths between s and t reduced problem: counting up to k + 1 simple paths between s and t restriction: class of graphs closed under edge removal
- 30. Other Benefits
- 31. Other Benefits relating the ambiguity of computation to that of the input graph
- 32. Other Benefits relating the ambiguity of computation to that of the input graph (minor) improvements of known results
- 33. Other Benefits relating the ambiguity of computation to that of the input graph (minor) improvements of known results (e.g., combining [Allender, Reinhardt] with [Buntrock et al.])
- 34. Thank You!