We propose a proof-theoretic approach for gaining evidence that certain parameterized problems are not fixed-parameter tractable. We consider proofs that witness that a given propositional formula cannot be satisfied by a truth assignment that sets at most k variables to true, considering k as the parameter. One could separate the ... more >>>
In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem
(ILP_{\bf R}) : Given a matrix A \in {\bf R}^{m \times n} and vectors
b \in {\bf R}^m, d \in {\bf R}^n, decide if there is $x ...
more >>>
In this paper we study the Boolean Knapsack problem (KP_{{\bf R}})
a^Tx=1, x \in \{0,1\}^n with real coefficients, in the framework
of the Blum-Shub-Smale real number computational model \cite{BSS}.
We obtain a new lower bound
\Omega \left( n\log n\right) \cdot f(1/a_{\min}) for the time
complexity ...
more >>>