On the Polynomial Time Computability of Abstract Ray-Tracing Problems(<Special Section>Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
The abstract ray-tracing problem asks, for a given scene consisting of a light source, a light receiver and finitely many obstacles in a space, and a given positive integer ε>0, whether a ray going out from the light source could reach the light receiver with intensity at least ε. The problem is known to be PSPACE-hard, and it is very unlikely that there exists an efficient algorithm to solve the problem without adding any restriction. In this paper, we show that the problem can be solved in polynomial time under some weak practical restrictions.
- 社団法人電子情報通信学会の論文
- 2005-05-01
著者
-
Isobe Shuji
Department Of Computer And Mathematical Sciences The Graduate School Of Information Sciences Tohoku
-
Isobe Shuji
Department Of Computer And Mathematical Sciences Graduate School Of Information Sciences Tohoku Univ
-
SHIZUYA Hiroki
Department of Computer and Mathematical Sciences, Graduate School of Information Sciences, Tohoku Un
-
Mambo Masahiro
Department Of Computer Science The Graduate School Of Systems And Information Engineering University
-
Shizuya Hiroki
Department Of Computer And Mathematical Sciences Graduate School Of Information Sciences Tohoku Univ
-
KURIYAMA Tetsuo
Department of Computer and Mathematical Sciences, the Graduate School of Information Sciences, Tohok
-
Shizuya Hiroki
Department Of Computer And Mathematical Sciences The Graduate School Of Information Sciences Tohoku
-
Kuriyama Tetsuo
Department Of Computer And Mathematical Sciences The Graduate School Of Information Sciences Tohoku
関連論文
- NPMV-Complete Functions That Compute Discrete Logarithms and Integer Factorization
- On the Difficulty of Searching for a String without Decryption (Special Section on Cryptography and Information Security)
- Making Cryptographic Primitives Harder
- Toward Separating Integer Factoring from Discrete Logarithm mod p(Foundations,Cryptography and Information Security)
- On the Polynomial Time Computability of Abstract Ray-Tracing Problems(Discrete Mathematics and Its Applications)
- On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions
- On the Length-Decreasing Self-Reducibility and the Many-One-Like Reducibilities for Partial Multivalued Functions