Gehinnn

10 ms·

61.
by Gehinnn 4y ago
Can you recommend an accessible proof for this? (is this simply because if the error probability is too low, it must be zero?) Are there problems in BPP that can defend against "helping" PRNGs by diagonalizing against them somehow
62.
Mathematicians have finally discovered an elusive ‘Einstein’ tile(sciencenews.org)
2 points by Gehinnn 4y ago|0 comments
63.
by Gehinnn 4y ago
You can also mix problems to change the average complexity. Take SAT (in NPC) and encode each instance with a word over a binary alphabet (eg. A and B). Then add 2SAT (in POLY) and encode it using an alphabet with four letters (eg. A, B, C
64.
by Gehinnn 4y ago
The 3 way merge editor actually shows the branch name!
65.
by Gehinnn 4y ago
This Syntax has the flaw that autocomplete cannot assist you before the from import clause has been added...
66.
by Gehinnn 4y ago
The new 3 way merge editor in VS Code tries to load the documents for base, yours and theirs from the corresponding commit URI, so that extensions such as gitlens can show the line history for each document - they don't even have to kn
67.
by Gehinnn 4y ago
You can also mix problems to change the average complexity. Take SAT (in NPC) and encode each instance with a word over a binary alphabet. Then add 2SAT (in POLY) and encode it using an alphabet with four letters. If you chose a random inst
68.
by Gehinnn 4y ago
"If halt can be implemented by using .length that means you can reduce .length to halt." This is true. The condition is false (halt cannot be implemented by using length), thus the implication is true, regardless of the implicant.
69.
by Gehinnn 4y ago
Why would this distinction matter for the argument?
70.
by Gehinnn 4y ago
Your reasoning is valid, and I do have the impression that you should refresh your knowledge about logic.
71.
by Gehinnn 4y ago
If you assume that halt does exist to make your solution valid, then you can derive any statement (including that addition does not exist), because that assumption is false. In general: Let P be a statement. Lets assume that the Turing Mach
72.
by Gehinnn 4y ago
This is not false. If you can implement halt using addition, addition cannot exist. Ex falso quod libet - if you can prove a single false statement, every statement is true.
73.
by Gehinnn 4y ago
Don't call you integer bound vars `start` and `end` please. Either use `start` and `endExclusive` or start and length - this greatly reduces confusion. In my experience, half opened integer intervals lead to fewer `- 1` in the code.
74.
by Gehinnn 4y ago
It is a very interesting idea to decompose a diff into two diffs - one part that a computer understands (like renames, formatting changes), and one part that a computer does not understand, but that is as small as possible! The referenced i
75.
by Gehinnn 4y ago
In case of the diff viewer in VS Code, the goal is to present the changes to the user in a helpful way, so that the user quickly understands what changed. In case of the merge editor, the diffs should reflect the actual edits as close as po
76.
by Gehinnn 4y ago
I just worked on a new diff algorithm for VS Code, in particular for the new merge editor (you can turn it on with "diffEditor.diffAlgorithm": "experimental"). Diffing is hard and there are many subtleties (e.g. https:&
77.
by Gehinnn 4y ago
> [...] mathematics can lead one to the conclusion that behind the veil of life there is a structure and an order. Rule 30, the collatz conjecture and the monster group let me to the conclusion that even math is chaotic.
78.
by Gehinnn 4y ago
Is there an existing open source effort to recreate that tool? Are the algorithms open? Does the tool work reliably? I find it very sad that potentially revolutionary progress is lost like this...
79.
by Gehinnn 4y ago
Semantic merge is no longer available? :(
80.
by Gehinnn 4y ago
It would be so cool if there was a json output, so that other tools (eg VS Code) can use this diffing algorithm! Thanks for explaining the algorithm!
81.
by Gehinnn 4y ago
I find this thought funny: The faster the reduction, the stronger the lower bound. When you reduce all-pair-shortest-paths (assuming a cubic lower bound) to your problem in quadratic time, your problem has a lower bound of linear time. Howe
82.
by Gehinnn 4y ago
But it uses a shared zstd dictionary among rows! The details are described here: https://phiresky.github.io/blog/2022/sqlite-zstd/
83.
by Gehinnn 4y ago
Finger trees. They work on an arbitrary monoid and maintain a list of items. You can insert and remove items in logarithmic time, as well as ask for the sum of items in a given range, also in logarithmic time. This is useful for example whe
84.
by Gehinnn 4y ago
White could win without zugzwang! Because white starts. After the first move, the position is no longer symmetric, so it doesn't help black to skip to switch sides.
85.
by Gehinnn 4y ago
Well, applying "zugzwang" means you only win because the opponent has to do a move and cannot skip their turn. When black has a winning strategy, black already applies "zugzwang" for white's very first move: Black o
86.
by Gehinnn 4y ago
The question was if there is any other scenario where black could force a win other than by forcing a zugzwang. I would say no by contradiction. Let's assume black could win without zugzwang. Then white would win (and in particular no
87.
by Gehinnn 4y ago
Zugzwang is the only way for white to lose. Without Zugzwang and a winning strategy for black for chess with Zugzwang, white could skip the first move and now has the winning strategy.
88.
by Gehinnn 4y ago
Why is that the consensus guess? I could imagine that a perfect play completely contradicts common chess theory. Just like we can efficiently find approximate solutions for the traveling salesman problem (that are at most 50% longer than th
89.
by Gehinnn 4y ago
That's not the meaning of turing completeness, just an implication of the space hierarchy theorems. There are systems that also have branching and unbounded memory, but are not turing complete. Context free grammars for example. Turing
90.
by Gehinnn 4y ago
The mistake is in step 7. You cannot calculate the expected value (of the envelope you get, when you pick one randomly and then swap) like that, as A is not a constant and actually depends on if you took the less or more valuable envelope i

More ›