Skip to main content
added 91 characters in body
Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

I'm afraid solving your problem in polynomial time is not possible unless P=NP. (Notice that the input size here is a polynomial in $|T|$ and $\log k$, but not $k$.)

If one can solve your problem in polynomial time, then using such solution algorithm $P(T,k)$ and binary search (in the virtual array of subsets of $T$ sorted by their sums, where $k$-th element is accessed with $P(T,k)$), it would be possible to solve the Subset Sum Problem in polynomial time as well. But the latter problem is NP-complete.

I'm afraid solving your problem in polynomial time is not possible unless P=NP.

If one can solve your problem in polynomial time, then using such solution algorithm $P(T,k)$ and binary search (in the virtual array of subsets of $T$ sorted by their sums, where $k$-th element is accessed with $P(T,k)$), it would be possible to solve the Subset Sum Problem in polynomial time as well. But the latter problem is NP-complete.

I'm afraid solving your problem in polynomial time is not possible unless P=NP. (Notice that the input size here is a polynomial in $|T|$ and $\log k$, but not $k$.)

If one can solve your problem in polynomial time, then using such solution algorithm $P(T,k)$ and binary search (in the virtual array of subsets of $T$ sorted by their sums, where $k$-th element is accessed with $P(T,k)$), it would be possible to solve the Subset Sum Problem in polynomial time as well. But the latter problem is NP-complete.

link and more details
Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

I'm afraid solving your problem in polynomial time is not possible unless P=NP. 

If one can solve your problem in polynomial time, then using thissuch solution algorithm $P(T,k)$ and binary searchbinary search (in the virtual array of subsets of $T$ sorted by their sums, where $k$-th element is accessed with $P(T,k)$), it would be possible to solve the Subset Sum problemProblem in polynomial time as well. But the latter problem is NP-complete.

I'm afraid solving your problem in polynomial time is not possible unless P=NP. If one can solve your problem in polynomial time, then using this solution and binary search, it would be possible to solve the Subset Sum problem in polynomial time as well. But the latter problem is NP-complete.

I'm afraid solving your problem in polynomial time is not possible unless P=NP. 

If one can solve your problem in polynomial time, then using such solution algorithm $P(T,k)$ and binary search (in the virtual array of subsets of $T$ sorted by their sums, where $k$-th element is accessed with $P(T,k)$), it would be possible to solve the Subset Sum Problem in polynomial time as well. But the latter problem is NP-complete.

added 35 characters in body
Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

I'm afraid thissolving your problem in polynomial time is not possible unless P=NP. If one can solve your problem in polynomial time, then using this solution and binary search, it would be possible to solve the Subset Sum problem in polynomial time as well. But the latter problem is NP-complete.

I'm afraid this is not possible unless P=NP. If one can solve your problem in polynomial time, then using this solution and binary search, it would be possible to solve the Subset Sum problem in polynomial time as well. But the latter problem is NP-complete.

I'm afraid solving your problem in polynomial time is not possible unless P=NP. If one can solve your problem in polynomial time, then using this solution and binary search, it would be possible to solve the Subset Sum problem in polynomial time as well. But the latter problem is NP-complete.

Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152
Loading