恶臭
发表于 2025-3-28 15:07:18
LOGSPACE, Random Walks on Graphs, and Universal Traversal Sequences,There is a surprising, at first glance unexpected, difference in (space) complexity between the problems of finding a path from a start node to an end node in a directed graph and of doing so in an undirected graph. In an undirected graph this is easier to solve; in fact, in can be done using a random walk or a universal traversal sequence.
Armory
发表于 2025-3-28 21:33:45
http://reply.papertrans.cn/39/3815/381479/381479_42.png
NAUT
发表于 2025-3-29 02:05:22
Spectral Problems and Descriptive Complexity Theory,This chapter begins with a question from predicate logic, namely to determine the set of all (sizes of) finite models of a given formula. It turns out that there is an amazingly close relationship between this question and the world of P and NP.
控制
发表于 2025-3-29 05:34:13
http://reply.papertrans.cn/39/3815/381479/381479_44.png
DEBT
发表于 2025-3-29 07:58:23
http://reply.papertrans.cn/39/3815/381479/381479_45.png
progestogen
发表于 2025-3-29 12:20:32
Lower Bounds for the Parity Function,In their pioneering work of 1984, Furst, Saxe and Sipser introduced the method of “random restrictions” to achieve lower bounds for circuits: The parity function cannot be computed by an AND-OR circuit of polynomial size and constant depth.
condone
发表于 2025-3-29 17:20:42
http://reply.papertrans.cn/39/3815/381479/381479_47.png
Foreshadow
发表于 2025-3-29 22:04:36
http://reply.papertrans.cn/39/3815/381479/381479_48.png
孤独无助
发表于 2025-3-30 01:44:39
The Berman-Hartmanis Conjecture and Sparse Sets,If all NP-complete languages were P-isomorphic to each other, then it would follow that P ≠ NP. This “Isomorphism Conjecture” has been the starting point of much research, in particular into sparse sets and their potential to be NP-complete.
牲畜栏
发表于 2025-3-30 05:28:09
http://reply.papertrans.cn/39/3815/381479/381479_50.png