Kyle Jones
  • Member for 9 years, 10 months
  • Last seen this week
  • Seattle, WA
What is the "formula" for "any cipher can be deciphered by a quantum computer"?
1 votes

In general, if NP turns out to be the subset of any tractable class then that will be a black swan event for those who depend on cryptography as it exists today. $NP \subseteq BQP$ is one such ...

View answer
Is this possible that quantum computer will be able to violate the Church thesis?
1 votes

As far as we know right now, no. Quantum computation makes some problems tractable that are currently intractable for classical computers, but problems that are theoretically impossible for classical ...

View answer
How to tell if a minimax search tree is computationally feasible using parallel computing
Accepted answer
1 votes

Plainly, evaluating $10^{19}$ positions is not going to be feasible in 7200 seconds. But if you use alpha-beta to prune the search tree and have perfect move ordering you can get that down to around $...

View answer
Playing video games to solve SAT instances
Accepted answer
1 votes

Given a SAT instance A, another SAT instance B can be constructed such that if it is found satisfiable the satisfying assignment proves the unsatisfiability of A. But the proof is one-sided; if B is ...

View answer
Why isn't SAT in coNP?
1 votes

So far as we know, NP and co-NP are separate complexity classes under Karp reduction, aka many-one polynomial-time reduction. Your procedure is a Turing reduction, not a Karp reduction. Turing ...

View answer
Why NAT is a disadvantage when TCP source port field is 16 bits?
1 votes

The practical limit to the number of hosts that can use a single NAT'd address is much less than 61,440. This is because even a modest Internet-capable computer will use many simultaneous TCP ...

View answer
binary representation of ip prefixes
1 votes

For a netmasked IP address xxx.xxx.xxx.xxx/N, convert each xxx octet in the address to binary. The masked address is the leftmost N bits with all other bits replaced with zeroes. So 10.0.0.2/2 ...

View answer
How does a File System handle an internal edit to a file?
1 votes

Filesystems typically don't handle internal edits to files as you describe them. When you edit a program file, a text editor will pull the whole file into memory, allow you to make modifications to a ...

View answer
Encoding order relations in CNF
1 votes

Variable $a_i$ set means class $a$ is in timeslot $i$, with a similar encoding for class $b$. Higher values of $i$ means later time slots. If class $a$ must occur before class b then you need ...

View answer
n-DNF boolean formula k satisfiability
1 votes

Your problem can't be any easier than DNF-TAUTOLOGIES since that problem is produced by setting $k$ equal to $2^n$. Therefore your problem is NP-hard, just as DNF-TAUTOLOGIES is.

View answer
Why not do these checks on the number of clauses in 3-SAT?
Accepted answer
1 votes

There's no real reason not to do your checks given that they are computationally tractable, but there's very little point in doing them either. Your checks make determining the satisfiability of easy ...

View answer
SAT for positive CNF clauses with exactly half of the variables being true
Accepted answer
1 votes

Your problem is NP-complete by the modern presentation of Schaefer's dichotomy theorem. You can also prove its NP-completeness by direct reduction of SAT to your problem. If a CNF formula has $n$ ...

View answer
time complexity of erasing repeated entries
1 votes

The basic algorithm is to first put all the members of S into a hash table $\mathcal{S}$. Then walk down the list T, recording its elements in a hash table $\mathcal{T}$ as you go. If an element has ...

View answer
Finding a solution to a satisfiable formula
1 votes

We don't know if any families of SAT formulas are hard since we don't yet know if P and NP are distinct complexity classes. Schaefer's dichotomy theorem gives six families of formulas that are known ...

View answer
Correctness of following algorithm for 3-QCNF?
1 votes

Your code ignores quantification levels. Formulas prefixed with $\exists{x_1}\forall{x_2}$ are not supposed to be evaluated the same way as those prefixed with $\forall{x_1}\exists{x_2}$. Your code ...

View answer
Is converting boolean formulas to sum-of-products a hard problem?
Accepted answer
1 votes

Your reasoning is correct. Your "sum-of-products" is more commonly known as disjunctive normal form (DNF). It is easy to show that conversion from conjunctive normal form (CNF) to DNF is NP-hard, so ...

View answer
Do iterative DNS queries return results from the servers cache?
1 votes

Cached data about a domain for which a DNS server is not authoritative could only have come from prior recursive queries. If you send a query without the RD (recursion desired) bit set, the server is ...

View answer
What this subnetting restriction means
Accepted answer
1 votes

Since each place in a binary number is a power of two, the binary expansion of $2^k$ for any $k$ will be a 1 followed by $k$ zeroes. Examples: $$1 = 2^0 = 1$$ $$16 = 2^4 = 1\underbrace{0000}_{4\ ...

View answer
Are NP-complete sets formed from two other sets only if at least one is NP-hard?
1 votes

The intersection of two non-NP-hard languages can be NP-hard. Example: The solutions of any 3SAT instance are the set intersection of the solutions of a HORN-3SAT instance and an ANTIHORN-3SAT ...

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
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
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
Neural Network Weights per input nodes
Accepted answer
1 votes

Yes, each input value is weighted before being fed into the nodes in the next layer. Each input/output pair of "neurons" has its own weight and it is these weights that are adjusted by the neural ...

View answer
Example for an unsatisfiable formula that can be made satisfiable by reordering quantifiers
1 votes

This $\qquad \forall x \exists z \space (x = z)$ is a true QBF. Whatever Boolean value $x$ is set to, $z$ can be set to match. Translated to quantified CNF: $\qquad \forall x \exists z \space (x \...

View answer
Quantifier String Placement
1 votes

If, as I suspect, you are still trying to convert quantified 3-CNF formulas into quantified mixed Horn formulas, the answer is that quantifiers for the newly added bridge variables can be placed ...

View answer
Application of Combinatorics, Logic and computability theory in physical science: Tiling of Wang Tile with proportionality
Accepted answer
1 votes

Use a SAT solver that also allows you to express pseudo-Boolean constraints. Encoding the verification of the existence of the tiling of an NxN grid as a CNF formula is straightforward. Each grid ...

View answer
What are flops and how are they benchmarked?
1 votes

Apple has just proudly stated that their new mac pro will be able to give up to 7 teraflops of computing power. Flops stands for Floating Point Operations Per Second. How exactly is this benchmarked ...

View answer
Must a deadlock necessarily occur if the four conditions exist?
1 votes

If the four Coffman conditions exist, you have an existing deadlock. The circular wait condition guarantees at least two blocked processes exist, each waiting for a resource held by the other. The ...

View answer