On the computational hardness based on linear FPT-reductions |
| |
| Authors: | Jianer Chen Xiuzhen Huang Iyad A. Kanj Ge Xia |
| |
| Affiliation: | (1) Department of Computer Science, Texas A&M University, College Station, TX 7843-3112, USA;(2) School of Information Science and Engineering, Central South University, Changsha, Hunan, 410083, China;(3) Computer Science Department, Arkansas State University, State University, Arkansas, 72467, USA;(4) School of CTI, DePaul University, 243 S. Wabash Avenue, Chicago, IL 60604, USA;(5) Department of Computer Science, Lafayette College, Easton, PA 18042, USA |
| |
| Abstract: | The notion of linear fpt-reductions has been recently introduced to derive strong computational lower bounds for well-known NP-hard problems. In this paper, we formally investigate the notion of W[t]-hardness under the linear fpt-reduction, and study the structural properties of the corresponding complexity classes. Additional complexity lower bounds on important computational problems are established. Some observations on structural properties of the standard parameterized hierarchy, the W -hierarchy, are also presented. In this paper, we always assume that complexity functions are “nice” with both domain and range being non-negative integers and the values of the functions and their inverses can be easily computed. |
| |
| Keywords: | FPT-reduction Linear Hardness Complexity |
| 本文献已被 SpringerLink 等数据库收录！ |
|
