2024-03-28T22:39:32Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002065162023-04-27T10:00:04Z01164:02592:10084:10299
What Restrictions Naturally Allow Well-Known NP-Complete Problems to Yield NL-Completeness and the Linear Space Hypothesis?What Restrictions Naturally Allow Well-Known NP-Complete Problems to Yield NL-Completeness and the Linear Space Hypothesis?enghttp://id.nii.ac.jp/1001/00206416/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=206516&item_no=1&attribute_id=1&file_no=1Copyright (c) 2020 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG.Faculty of Engineering, University of FukuiTomoyuki, YamakamiMany practical combinatorial problems have been shown to be NP-complete or NP-hard. To cope with further real-life situations of those problems, we are often focused on their subproblems obtained naturally by imposing reasonable restrictions onto their instances or their key properties. Those subproblems in general turn out to have much lower complexity than the original problems do. We are interested in what types of restrictions significantly affect the computational complexities of most well-known NP-complete problems. In particular, we seek natural restrictions that force various NP-complete problems to become NL-complete. With further restrictions, we may make their parameterizations equivalent to a practical working hypothesis, known as the linear space hypothesis (LSH), which is related to the space complexity upper bound of a weak form of the parameterized 2SAT. As a direct consequence, under the assumption of LSH, we obtain sub-linear lower bounds on the space complexity necessary to solve various NL-complete problems within polynomially many steps.Many practical combinatorial problems have been shown to be NP-complete or NP-hard. To cope with further real-life situations of those problems, we are often focused on their subproblems obtained naturally by imposing reasonable restrictions onto their instances or their key properties. Those subproblems in general turn out to have much lower complexity than the original problems do. We are interested in what types of restrictions significantly affect the computational complexities of most well-known NP-complete problems. In particular, we seek natural restrictions that force various NP-complete problems to become NL-complete. With further restrictions, we may make their parameterizations equivalent to a practical working hypothesis, known as the linear space hypothesis (LSH), which is related to the space complexity upper bound of a weak form of the parameterized 2SAT. As a direct consequence, under the assumption of LSH, we obtain sub-linear lower bounds on the space complexity necessary to solve various NL-complete problems within polynomially many steps.AN1009593X研究報告アルゴリズム(AL)2020-AL-1798182020-08-252188-85662020-08-20