Skip to main content
Computer Science

Return to Question

Post Timeline

added 981 characters in body
Source Link
Cryptonaut
Cryptonaut
  • 299
  • 2
  • 11

Are there any known upper/lower bounds on the size of a witness of some np-complete/hard problem, or more precisely the relation between the problem size and the witness size. For example, I'm interested in subset sum, set cover, SAT, hamiltonian cycles. If there is something known for other problems, I'd also be interested. To be a bit more clear, I'll explain what I mean in detail for two of those problems.

Imagine you have a subset sumUPDATE: I assume the problem has a solution. The list of all integers So I am not interested in the decision version, but rather I assume there does exist a (the statementpositive) is probably bigger than the actual set of numbers that are part of the witnesssolution and I'm trying to find it. What

For example, I give you a SAT problem and I tell you there is the smallest/biggest size a the witness subsetsolution, splease find at least one.t This should also be NP-complete. thatNow if the problemSAT Problem has 3 literals, it's easy to solve. If it has n/2 literals and n clauses, it's probably not easy. So my question is still hard?at what point it becomes easy and why.

In the case of SATsubset sum. I am interested ingive you a subset sum problem instance and ask you to find me one of the relation betweensolutions, which I tell you exist. This is still hard to do, but is it also hard to do if I tell you that the/a solution will be a subset of number of distinct literals and the size n/2 for a list of length n? Again, I'm interested in understanding at which sizes of the formulasolution the problem becomes easy. That is how much bigger does or can

For hamiltonian cycles, I ask you to find a formula becycle of size $k$ in comparison toa graph of size $n$, for which $k$ is the total numberproblem hard and so on...

I looked at the analysis of literalsFixed Tractable Problems, but they seem to focus on parameters that are fixed to constants, which is not necessarily what I want to know I think.

My intuition would be that most (NP-hard) search problems become easy once the witness size is smaller than $log(n)$ or bigger than $n-log(n)$, but I don't know how to actually support this claim formally.

I hope my question is a bit clearer now.

Are there any known upper/lower bounds on the size of a witness of some np-complete/hard problem, or more precisely the relation between the problem size and the witness size. For example, I'm interested in subset sum, set cover, SAT, hamiltonian cycles. If there is something known for other problems, I'd also be interested. To be a bit more clear, I'll explain what I mean in detail for two of those problems.

Imagine you have a subset sum problem. The list of all integers (the statement) is probably bigger than the actual set of numbers that are part of the witness. What is the smallest/biggest size a the witness subset, s.t. that the problem is still hard?

In the case of SAT I am interested in the relation between the number of distinct literals and the size of the formula. That is how much bigger does or can a formula be in comparison to the total number of literals.

Are there any known upper/lower bounds on the size of a witness of some np-complete/hard problem, or more precisely the relation between the problem size and the witness size. For example, I'm interested in subset sum, set cover, SAT, hamiltonian cycles. If there is something known for other problems, I'd also be interested. To be a bit more clear, I'll explain what I mean in detail for two of those problems.

UPDATE: I assume the problem has a solution. So I am not interested in the decision version, but rather I assume there does exist a (positive) solution and I'm trying to find it.

For example, I give you a SAT problem and I tell you there is a solution, please find at least one. This should also be NP-complete. Now if the SAT Problem has 3 literals, it's easy to solve. If it has n/2 literals and n clauses, it's probably not easy. So my question is at what point it becomes easy and why.

In the case of subset sum. I give you a subset sum problem instance and ask you to find me one of the solutions, which I tell you exist. This is still hard to do, but is it also hard to do if I tell you that the/a solution will be a subset of number of size n/2 for a list of length n? Again, I'm interested in understanding at which sizes of the solution the problem becomes easy.

For hamiltonian cycles, I ask you to find a cycle of size $k$ in a graph of size $n$, for which $k$ is the problem hard and so on...

I looked at the analysis of Fixed Tractable Problems, but they seem to focus on parameters that are fixed to constants, which is not necessarily what I want to know I think.

My intuition would be that most (NP-hard) search problems become easy once the witness size is smaller than $log(n)$ or bigger than $n-log(n)$, but I don't know how to actually support this claim formally.

I hope my question is a bit clearer now.

edited tags
Link
Raphael
Raphael
  • 73.4k
  • 31
  • 184
  • 408
Source Link
Cryptonaut
Cryptonaut
  • 299
  • 2
  • 11

Relation between witness and problem statement

Are there any known upper/lower bounds on the size of a witness of some np-complete/hard problem, or more precisely the relation between the problem size and the witness size. For example, I'm interested in subset sum, set cover, SAT, hamiltonian cycles. If there is something known for other problems, I'd also be interested. To be a bit more clear, I'll explain what I mean in detail for two of those problems.

Imagine you have a subset sum problem. The list of all integers (the statement) is probably bigger than the actual set of numbers that are part of the witness. What is the smallest/biggest size a the witness subset, s.t. that the problem is still hard?

In the case of SAT I am interested in the relation between the number of distinct literals and the size of the formula. That is how much bigger does or can a formula be in comparison to the total number of literals.