Another hack search problem solvable in polynomial time by a nondeterministic machine but not by a deterministic one. But it's not a proper problem. Suppose you have an infinitely large RAM of random numbers (yeah, this starts out real well). The problem is to find if an nbit number exists in the first 2^n bits of the RAM.
As usual, the deterministic machine has to scan the RAM to find the number, taking around 2^n steps. And as usual, the nondeterministic machine just guesses the n bits of the address in n steps and passes it to checkSolution, which jumps to the address and confirms the solution. Now, this is not an NPcomplete problem in this formulation, since the contents of the RAM are not specified, so there's no mapping from other NPcomplete problems to this.
Jeez, random numbers.
Given the lottery numbers for this week's lottery, compute the lottery numbers for next week's lottery. Nondeterministic machine: sure thing, done, bam. Deterministic machine: this might take a while (btw, is simulating the universe a O(n^k)problem?) Check solution by checking bank account.
Unique inputs partial sums then. First off, sort the inputs, and treat them as a binary number where 0 is "not in solution" and 1 is "in solution".
If all the numbers in the input are such that the sum of all smaller inputs is smaller than the number, you can find the solution in linear time. For (i = input.length1 to 0) { if (input[i] <= target) { target_bits[i] = 1; target = input[i]; } else { target_bits[i] = 0; }}
You can prune the search space by finding a suffix that's larger than the target and by finding a prefix that's smaller than the target. Now you know that there must be at least one 0bit in the larger suffix and at least one 1bit in the suffix of the smaller prefix.
The time complexity of partial sums is always smaller than 2^n. For a onebit alphabet, the time complexity is O(n). For a twobit alphabet, the max time complexity is 2^(n/2) as you need to add two bits to the input to increment the number of elements in the input. So for an 8bit alphabet, the max complexity would be 2^(n/8).
The complexity of partial sums approaches easy as the number of input elements approaches the size of the input alphabet. After reaching the size of the input alphabet, a solution exists if (2^a + 1) * (2^a / 2) <= target (as in, if the sum of the input alphabet is greater than or equal to target. And if the input alphabet is a dense enumeration up from 1.) You can find the solution in O(n log n): sort input, start iterating from largest & deduct from the target until the current number is larger than the target. Then jump to input[target] to get the last number. You can also do this in O(n) by first figuring out what numbers you need and then collecting them from the input with if (required_numbers[input[i]]) pick(input[i]), required_numbers can be an array of size n.
Once you reach the saturated alphabet state, you need to increase the size of the alphabet to gain complexity. So you might go from an 8bit alphabet with a 256 element input to a 9bit alphabet with a 256 element input (jumping from 2048 to 2304 bits in the process, hopefully boosting the complexity from O(256)ish to O(2^256)ish).
Thankfully, as you increase the alphabet size by a bit, your input size goes up linearly, but the saturation point of your alphabet doubles. At a fixed input size in bits, increasing the alphabet size can decrease the complexity of the problem, for each bit increase you can go from 2^(n/k) > 2^(n/(k+1)). Likewise, by decreasing the alphabet size, you can increase the complexity of the problem. Increasing the number of elements in the input can increase the complexity of the problem, while decreasing the number of elements can decrease the complexity. The "can" is because it depends. If you're close to saturation, increasing the number of elements can nudge the problem from O(n^2) to O(n), ditto for decreasing the alphabet size. Whereas increasing the alphabet size at saturation can turn your O(n) problem into an O(2^n) problem.
As your alphabet gets larger, the discontinuities stop being so important. Anyhow, for a given partial sums input size in bits, the problem is O(n) for alphabet sizes <= log2(n). The difficulty of the problem scales with the target as well. For targets smaller than the smallest input element and for targets greater than the greatest input element, it takes O(n) time.
Tricks, hmm, the number of searchenhancing tricks you can use depends on the input. I guess the number of tricks is somehow related to the number of bits in the input and grows the program size too. The ultimate trick machine knows all the answers based on the input and has to do zero extra computation (yeah, this is the array of answers), but it's huge in size and requires you to solve the problem for all the inputs to actually write the program.
Oh well
art with code
20170824
Subscribe to:
Post Comments (Atom)
About Me

Ilmari Heikkinen
 Built art installations, web sites, graphics libraries, web browsers, mobile apps, desktop apps, media player themes, many nutty prototypes, much bad code, much bad art.Have freelanced for Verizon, Google, Mozilla, Warner Bros, Sony Pictures, Yahoo!, Microsoft, Valve Software, TDK Electronics.ExChrome Developer Relations.
Projects
 Filezoo  Minimalistic zoomable file manager
 Cake.js  JavaScript Canvas animation library
 Missile Fleet  A game written with Cake.js
 Gitbug  Inrepo bug tracker for Git
 Prelude.ml  OCaml stdlib replacement with a Haskellish flavour
 Metadata  File metadata extraction tool and Ruby library
 Thumbnailer  File thumbnailing tool and Ruby library
 Random canvas demos