焦虑
发表于 2025-3-23 11:43:55
Tally languages accepted by Monte Carlo pushdown automata,phabet. For instance, the class of languages recognizable by 1-way nondeterministic pushdown automata equals the class of the context-free languages, but the class of the tally languages recognizable by 1-way nondeterministic pushdown automata, contains only regular languages . We prove that l
谄媚于人
发表于 2025-3-23 15:29:19
http://reply.papertrans.cn/83/8212/821116/821116_12.png
SMART
发表于 2025-3-23 20:50:03
Randomness, stochasticity and approximations,h sets have optimal unsafe approximations has been investigated extensively, see, e.g., . Recently, Wang showed that polynomial time random sets are neither optimally unsafe approximable nor .-levelable. In this paper, we will show that: (1) There exists a polynomial time stoc
自传
发表于 2025-3-24 01:15:43
Probabilistic approximation of some NP optimization problems by finite-state machines, of n independent identically distributed random variables with a fixed distribution. Then for any ε > 0 there exists a finite-state machine which does the following: On a random input . the finite-state machine produces a feasible solution whose objective value . satisfies.when . is large enough. Here . and . are positive constants.
格子架
发表于 2025-3-24 05:58:50
http://reply.papertrans.cn/83/8212/821116/821116_15.png
overwrought
发表于 2025-3-24 10:26:41
http://reply.papertrans.cn/83/8212/821116/821116_16.png
affluent
发表于 2025-3-24 11:22:48
0302-9743 ce, RANDOM‘97, held as a satelite meeting of ICALP‘97, in Bologna, Italy, in July 1997..The volume presents 14 thoroughly revised full papers selected from 37 submissions; also included are four invited contributions by leading researchers. The book focuses on algorithms and complexity aspects arisi
火花
发表于 2025-3-24 17:23:25
Conference proceedings 1997‘97, held as a satelite meeting of ICALP‘97, in Bologna, Italy, in July 1997..The volume presents 14 thoroughly revised full papers selected from 37 submissions; also included are four invited contributions by leading researchers. The book focuses on algorithms and complexity aspects arising in the
自然环境
发表于 2025-3-24 21:15:24
Conference proceedings 1997ubmissions; also included are four invited contributions by leading researchers. The book focuses on algorithms and complexity aspects arising in the development of efficient randomized solutions to computationally difficult problems. The papers are organized in sections on approximation, randomness, algorithms, and complexity.
大漩涡
发表于 2025-3-25 00:08:04
A combinatorial consistency lemma with application to proving the PCP theorem,degree tests (which yields weaker bounds). In other words, we replace the strong algebraic analysis of low-degree tests presented by Arora and Safra and Arora et. al. by a combinatorial lemma (which does not refer to low-degree tests or polynomials).