## Find maximal subset with interesting weight function

You are given $$n$$ rows of positive integers of length $$k$$. We define a weight function for every subset of given $$n$$ rows as follows – for every $$i = 1, 2, \dots, k$$ take the maximum value of $$i$$-th column (), then add up all the maximums.

For example, for $$n = 4$$, $$k = 2$$ and rows $$(1, 4), (2, 3), (3, 2), (4, 1)$$ the weight of subset $$(1, 4), (2, 3), (3, 2)$$ is $$\max\{1, 2, 3\} + \max\{4, 3, 2\} = 3 + 4 = 7$$.

The question is, having $$m \leq n$$, find the subset of size $$m$$ (from given $$n$$ rows) with maximal weight.

The problem looks trivial when $$m \geq k$$, but how can one solve it for $$m < k$$? Looks like dynamic programming on subsets could work for small $$k$$, isn’t it? Are there other ways to do it?

Posted on Categories proxies

## Subset sum problem with a complication

I have a sorted list of numbers. I know they can be divided into two parts. I also know the sum of those 2 parts. I want to know what these subsets are. How can i find them? The size of my list can be ~ 10^6. The sum of my subsets can be ~ 10^24. Is there a better way to find my subset with a time complexity of O(n*sum) or O(n^2 logn) or is it not possible?

Posted on Categories proxies

## Determine if there is a subset of the given set with sum divisible by a given integer

I’ve been given a question to solve:

Given a set of non-negative distinct integers, and a value $$m$$, determine if there is a subset of the given set with sum divisible by $$m$$.

For this question the answer is here

I don’t understand the part after if DP[j]==True
what is actually the intuition behind this code. Please explain in detail.

Posted on Categories proxies

## Can partial Turing completeness be quantified as a subset of Turing-computable functions?

Can partial Turing completeness be coherently defined this way:
An an abstract machine or programming language can be construed as Turing complete on its computable subset of Turing-computable functions.

In computability theory, several closely related terms are used to describe the computational power of a computational system (such as an abstract machine or programming language):

Turing completeness A computational system that can compute every Turing-computable function is called Turing-complete (or Turing-powerful). https://en.wikipedia.org/wiki/Turing_completeness

Posted on Categories proxies

## Complexity of Subset Sum where the size of the subset is specified

I know it should be easy but I’m trying to determine the complexity of the following variant of Subset Sum.

Given a subset $$S$$ of positive integers and integers $$k>0$$ and $$N>0$$, is there a subset $$T\subset S$$ such that $$|T|=k$$ and the members of $$T$$ sum to $$N$$ ?

All of the formulations of subset sum that I’ve seen don’t specify $$k$$ so I’m wondering if this problem can be solved in polynomial time. If $$k$$ is fixed for all instances, then I know that the problem is in P and solvable by brute force in $$O(n^k)$$ time. However, I’m allowing $$k$$ to vary from instance to instance.

Posted on Categories proxies

## Reconstructing an Array via Time-Intensive Subset Queries

I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem.

I am given access to an array of numbers. However, I am only allowed to query it by specifying an arbitrary subset of indices, in response to which I am then given the sum of the elements at those positions. These queries are quite costly, specifically they run in time $$\tilde{O}(n^2)$$ time (where $$\tilde{O}(\cdot)$$ hides polylogarithmic factors). I want to determine the element at each index in the array (i.e. reconstruct the array) using as little time as possible.

Of course, it is possible to do this by querying each element on its own. This algorithm does $$n$$ queries and hence has total running time $$\tilde{O}(n^3)$$. I am wondering if there is a faster way. Adaptivity does not help with this problem, so any algorithm would have two steps: First, it executes a fixed sequence of queries, and then reconstructs all elements using the query answers. Ideally, both steps run in time $$o(n^3)$$. So far, any set of $$o(n)$$ queries that I looked at makes recovery impossible. This might be the case for any such set of queries (and my intuition screams that this is probably the case), but I cannot see a proof for this.

I’d love an answer that either shows a faster algorithm or proves that $$o(n)$$ queries are impossible, but answers with partial insights would also be great.

Posted on Categories proxies

I have a foreach loop for a custom post type ordered by date (meta key). If a post’s associated date is less than the current date (i.e., dates not in the future), I want to output some HTML. if ($custom_post_date >=$ today && $index === 1) The problem I am running into is that the HTML gets output after the first post that is in the past. How can I output the HTML before the first post that meets the criteria? Is there a way to go back in the foreach loop or something to that effect? ## Every decidable lanugage$L$has an infinite decidable subset$S \subset L$such that$L \setminus S\$ is infinite

Given an infinite decidable language $$L$$, then if $$S \subset L$$ such that $$L \setminus S$$ is finite, then $$S$$ must be decidable. This is true since given a decider of $$L$$ we contruct a decider for $$S$$:

Simulate the decider of $$L$$ on the input, if it accepts, go over $$L \setminus S$$ and check if it is there, if it is, reject. If it isn’t accept. If the decider of $$L$$ rejects – reject.

Another point is if $$S \subset L$$ is finite then $$S$$ also must be decidable, this is immediate that every finite language is decidable.

Now we have the last case where $$S$$ is infinite and $$L \setminus S$$ is infinite. We know that there must be some subsets $$S$$ corresponding to this case that are undecidable. This is since there are $$\aleph$$ such $$S$$ but only $$\aleph_0$$ deciders. Denote $$D(L) = \{ S \subset L : |S|= |L \setminus S|=\infty \wedge S \text{ is decidable} \}$$

Is it true that for all infinite decidable languages $$L$$ we have $$D(L) \neq \phi$$?

If this is true then as a conclusion we will have for all infinite decidable languages $$L$$ a sequence of decidable languages $$L_n$$ such that $$L_0=L$$ and $$L_{n+1} \subset L_n$$ and $$|L_n \setminus L_{n+1}| = \infty$$

We will also have a limit-set $$L_\infty = \{ e \in L : \forall n \in \mathbb{N} \text{ } e \in L_n \}$$ and can dicuss if it is empty/finite/infinite and decicable or not.

This seems like a nice way to study decidable languages, and curious to know if this direction is indeed interesting and whether there are articles published regarding these questions

Thanks for any help

Posted on Categories proxies

## need to address a subset of CIA triad elements and not in entirety

Its usually recommended that ‘don’t use your own system of Crypto’ rather use standard SSL/TLS! I understand that SSL/TLS is a complete protocol suite that addresses all three elements of CIA triad. What if I need to use a subset of CIA, say I just need Authentication and Data Integrity. In such a cases isn’t using full SSL/TLS is an overkill?

what’s the issue / risk, if I make and use a customized crypto suite which addresses my specific requirements like in this case for if I just need Authentication and Integrity, I use only digital signing of data with a digital certificate; and skip the encryption part of data (confidentiality is not a concern).

Posted on Categories proxies

## What is the time complexity of subset testing?

Consider the following problem:

Let $$A = \{a_1,…,a_n\}$$ and $$B = \{b_1,…,b_m\}$$ be two finite sets over $$\mathbb{N}$$. The sequences $$a_1,…,a_n$$ and $$b_1,…,b_m$$ do not have to be sorted. Given as inputs the strings $$a_1,…,a_n$$ and $$b_1,…,b_m$$, determine if $$A \subseteq B$$.

What is the time complexity of this problem?