Kyle Jones
  • Member for 9 years, 10 months
  • Last seen this week
  • Seattle, WA
Radix sort and changing bases
Accepted answer
2 votes

The asymptotic runtime ignores access times for the digits. On typical hardware a base 256 number can be manipulated faster than extracting base 10 digits from the same number. If you have multiple ...

View answer
How can a set offer better search performance than an array
Accepted answer
1 votes

I think the key is that NSSets aren't required to "maintain order," meaning that you cannot access elements with an index, nor can you extract elements in any particular order. Because NSSets don't ...

View answer
How to find a basis which is guaranteed to need 9 or less characters to represent a 12 digits number?
11 votes

The largest 12 digit number in base 10 is $10^{12} - 1$. In general the largest $n$ position number in a base $b$ is $b^{n} - 1$. So in your case you need a base large enough that $b^{9} - 1 > ...

View answer
Algorithm for finding all the combinations on a boolean array
2 votes

The pattern you're trying to match is regular and can be matched by the regular expression 1(0?1)*. A good strategy would be to convert the binary array to a string and do regular expression matches ...

View answer
Could an NP-hard problem have a mechanical or physical solution method?
Accepted answer
7 votes

Scott Aaronson examines "mechanical" solutions to NP-complete problems in the odd and entertaining paper "NP-complete Problems and Physical Reality". The paper is mostly theoretical discussions of ...

View answer
What is the name for the complexity class $O(n^{1+\epsilon})$
1 votes

The term I've seen in use is superlinear, as in "Are there super-linear time complexity lower bounds for any natural problem in NP?"

View answer
What is the appropriate algorithm for bipartite matching with constraints?
1 votes

The problem as described still seems amenable to doing a bipartite matching with weighted edges if you adapt the graph setup as follows. If an employee must do four jobs, represent the employee with ...

View answer
Why is this flow a max flow?
6 votes

You've left out part of the statement. It should be "If there's no path between the source and the sink with unused capacity the flow is a max flow." If you look at your graph you'll see that there ...

View answer
Algorithm for Dynamic Client Side Throttling
2 votes

Only the server can accurately determine what its current load is, and thus how much more work it can handle or when it might be able to handle more work in the future. This is why load balancing and ...

View answer
Why is the class NP-Complete important compared to NP-hard?
9 votes

From the point of view of someone who writes code for a living, having a good familiarity with NP-completeness is important for: 1. Recognizing when you're barking up the wrong tree NP-complete ...

View answer
Strongly connected components on a DAG
2 votes

I know of no convention; the right result depends entirely on what you want to do with the result. As an example, if you're trying to use strongly connected components to find satisfying assignments ...

View answer
Would it be possible to use the cloud for RAM?
Accepted answer
8 votes

Network latency is orders of magnitude too high for a remote server to usefully share its RAM directly, even if you could cobble together a virtualization layer to make it work. However, today's ...

View answer
Conflict Driven Clause Learning backtracking clarification
Accepted answer
7 votes

Here's the relevant paragraph from the MiniSAT paper: The decision phase will continue until either all variables have been assigned, in which case we have a model, or a conflict has occurred. On ...

View answer
What's wrong here, or, is CNF to DNF conversion in o(exp(n))?
Accepted answer
4 votes

Can we say that time complexity will also be within $o(exp(n))$, where $n$ denotes formula length? No, because no one has proven that distribution of terms is the only way to convert CNF to DNF. ...

View answer
Why don't modern SAT solvers use the notion of a "watched clause", in the same way they use the notion of a "watched literal"?
Accepted answer
11 votes

A typical SAT solver notices that a satisfying assignment has been found when there are no more variables to assign. So the only time that a SAT solver would save by early notification is the time it ...

View answer
Is 2-SAT with XOR-relations NP-complete?
Accepted answer
13 votes

2-SAT-with-XOR-relations can be proven NP-complete by reduction from 3-SAT. Any 3-SAT clause $$(x_1 \lor x_2 \lor x_3)$$ can be rewritten into the equisatisfiable 2-SAT-with-XOR-relations expression $...

View answer
If one shows that UNIQUE k-SAT is in P, does it imply P=NP?
Accepted answer
11 votes

This is still an open question; UP is not known to be equivalent to NP. In the paper "NP Might Not Be As Easy As Detecting Unique Solutions," Beigel, Burhman and Fortnow construct an oracle under ...

View answer
Basic question about backjumping in SAT solvers
Accepted answer
2 votes

The intervening assignments between the current assignment and the backjump point might have been arrived at via considerable backtracking and backjumping themselves and it would be wasteful to repeat ...

View answer
Is the Euclidean TSP weakly NP-hard?
Accepted answer
4 votes

You're confusing a polynomial time approximation scheme (PTAS) and a fully polynomial time approximation scheme (FPTAS). Euclidean TSP has a PTAS, but it is not an FPTAS because the polynomial ...

View answer
Reduction of Circuit Satisfiability to CNFSAT
2 votes

The exponential blowup when converting circuits to conjunctive normal form is avoided by introducing new variables to represent the output of each sub-circuit plus a simple set of rules represent each ...

View answer
Constrain certain variables in CNF to unique satisfying assignments
Accepted answer
1 votes

If you could add clauses to a CNF formula to cause it to be unsatisfiable iff certain sets of variables don't have non-unique assignments among the formula's satisfying assignments, you could use this ...

View answer
Why we need tagbits when we already have indexbit and offset?
1 votes

Multiple memory locations hash to the same location in the memory cache. The tag array serves to disambiguate which memory location's contents are stored in each cache location. If the address in ...

View answer
Why is the CPU Involved During Keyboard Echo?
Accepted answer
6 votes

Letting the computer see each character as it is typed allows programmers to make the user interface more dynamic. Back when a serious computer was the size of several upright refrigerators and ...

View answer
Is order of bits in byte really not of concern?
Accepted answer
9 votes

Bytes are transferred from memory to disk using an I/O protocol (e.g. SCSI) that specifies the bit order of transmission in the case of a serial protocol, or for parallel protocols specifies which pin ...

View answer
Applications of model counting
4 votes

A recurring application for SAT model counting in the literature is extracting predictions from Bayesian networks. See "Algorithms and Complexity Results for #SAT and Bayesian Inference" and "On ...

View answer
Why is DPLL better than brute force?
Accepted answer
7 votes

Local (stochastic) search is all about clever navigation of the search space. DPLL's advantage is pruning the search space of large swaths of assignments that provably cannot satisfy the formula. ...

View answer
Forward checking with conflict directed backjumping
Accepted answer
3 votes

If forward checking detects that the potential assignment of a variable $x_1$ leaves no valid assignments for the variable $x_2$, one simple strategy is to just make the assignment to $x_1$ and then ...

View answer
About sorting numbers in linear time
4 votes

Radix sorting runs in time $O(dn)$ where $d$ is the number of digits in each key and $n$ is the number of keys to be sorted. This is of course linear time only if $d$ is a constant. If the keys are ...

View answer
How exactly do you calculate the hidden layer gradients in the backpropagation algorithm?
Accepted answer
3 votes

You've transposed the sizes of both $w^L$ and $\delta^{x,L}$. $w^L$ should be 2x4 and $\delta^{x,L}$ should be 2x1. $(w^L)^T$ is a 4x2 matrix that will be multipled by a 2x1 matrix yielding a 4x1 ...

View answer
I am having trouble understanding (and implementing) logistic regression for classifying into three classes
Accepted answer
7 votes

How do you apply the weight vector to the sample to get a classification out of it for 3 classes (not just two). If you have $n$ possible classes then you must train $n$ logistic classifiers on your ...

View answer