Forgot your password?
typodupeerror

Comment: Re:so just don't solve it (Score 1) 169

by allo (#48252609) Attached to: Tetris Is Hard To Test

Best is only with respect to the deterministic case.

disregard runtime complexity.

deterministic:
there is a best strategy (A).
all other strategies (B) are worse or equal.
A stochastic strategy (C) may have a good average quality.

stochastic:
the deterministic best strategy (A) cannot be perfect anymore, just as no other strategy can.
(A) has now unknown quality for a random sequence.
(C) still has the same average quality.

So there is now a possibility, that (C) may beat (A) in an average over a lot of games. (as a single game does not have any relevance when using random games)

Comment: Re:if I understand your point (Score 2) 169

by allo (#48242777) Attached to: Tetris Is Hard To Test

no, you got it only the half way.

deterministic:
best = np-hard, perfekt
other: polynomial, good average

stochastic:
best: np-hard, not perfect, quality unknown
other: polynomial, good average

the point is not the runtime complexity, but the result. while the best algorithm cannot be beaten on the det. sequence, it may fail completely (in terms of quality) on a sequence without full information. If you got a good polynomial one with an average result, it may be better for many sequences.

one example may be an perfect algorithm with a lookup table for all sequences and a greedy algorithm.
With the random sequence, the "perfect" algorithm needs to choose the sequence which is most likely for its next move, discarding a lot of other strategies. Now it may have chosen the worst strategy for the next random and unlikely event. The other algorithm optimizes locally anyway and will continue in both cases as if it does not know the next event.

Comment: Re:defined as expected value (Score 2) 169

by allo (#48235121) Attached to: Tetris Is Hard To Test

Jep, and your strategy gets worse, while another strategy may stay average.

Assume you flip a coin. heads or tails.

You NP-complete algorithm knows the sequence.
The probalistic one just guesses "heads".

Now the Expectation value of both are Zero in the stochastic case. In the deterministic one its infinite win for the np-complete one and zero for the probalistic one.
So this is an example, where a perfect algorithm for deterministic data is just as good as another for stochastic data.
This does not mean, you cannot get better than the deterministic-optimal algorithm. As the data is random, the deterministic-optimal algorithm becomes "just another algorithm" and you will need to proof again its better than the other candidates. It may be, maybe even provable the still the optimal one, but the fact that its det-optimal does not imply that its prob-optimal.

A real world example: Las Vegas Quicksort.
Quicksort is O(n log n), choosing log n times a median element, then sorting in n the elements on both sides to the correct side.

calculating the median element is O(n), with some constant C.
Choosing the median element randomly is O(1).
Now you can show, that the propability of a "not too bad" element is so, that the log n * C factor is slower in most cases than the slowdown of the algorithm by choosing a non-optimal "median".

Comment: Re:What do you mean? (Score 1) 266

by allo (#48234311) Attached to: Jedi-ism Becomes a Serious Religion

Indeed, one of the best ideas for calendars ever. 5 seasons is reasonable, ~73 days is not perfectly round, but 30/31/28 is strange, too. Now combine it with @beats (1000 beats are one day) and you have an ideal system for measuring time. You just do not get a metric number of days per year, because we would need to change the earth orbit to keep the day and night schedule.

Comment: Re:perhaps. I wonder if it NP-hard (Score 3, Informative) 169

by allo (#48233041) Attached to: Tetris Is Hard To Test

I disagree.
For a stochastic process your greedy "take the option with the best chance" algorithm may work, it may fail completely, just depending on the random numbers. If you have an stochastic polynomial algorithm, you have a chance to get the same or better expectation value than your "optimize global then choose greedy" algorithm. Both approaches may win or fail, but in the deterministic game the np-complete version always wins, while the "shortcut" version cannot compete. In the stochastic version, the shortcut may be as good as the optimal solution, because you cannot get the global optimum anyway so choosing a local one may be a good choice.

Comment: Re: Is there a way to prevent this? (Score 1) 206

by allo (#48231321) Attached to: Verizon Injects Unique IDs Into HTTP Traffic

you're still not getting the szenario, just as i did not in my first post.

VZW does not want to interfere for this szenario. They interfere with http adding an id and ignore https. The website wants your identification. So they generate a token on the https-site and load image.jpg?token from a http(without s) site. Then they know a token vzw correlation and can assign the same token on your next visit.

Hello supercookies.

Comment: Re: Is there a way to prevent this? (Score 1) 206

by allo (#48230163) Attached to: Verizon Injects Unique IDs Into HTTP Traffic

nope, he's right. Your adversary is the site, not verizon. And the site can make you request non-http stuff, where verizon (which is not the main enemy) injects an id, which can then be read by the site. There is not much protection without using extreme measures like requestpolicy (and not allowing anything using http).

Comment: Re:Drop owncloud (Score 1) 126

by allo (#48230145) Attached to: OwnCloud Dev Requests Removal From Ubuntu Repos Over Security Holes

Meh, what did the user do before owncloud, which is a rather home grown software? I did not test a lot of groupwares, but i am aware, that there are many to choose from, with many users. Some are very old already and i guess they have many of the features a normal users needs. tine looks nice, horde is more mailcentric, egroupware is some other name i never tested ... and you can combine single products. While owncloud is nice and each feature is not too bad, there is another more complete software for each feature, which is just not integrating into a single product, which is the advantage of owncloud.

Comment: Re:Drop owncloud (Score 1) 126

by allo (#48229121) Attached to: OwnCloud Dev Requests Removal From Ubuntu Repos Over Security Holes

yep, its a filesync tool.

for calendar and contacts you may still consider owncloud, but there are a lot of "groupwares", which do a fine job.
owncloud tries to do everything ... which gives quite a cloud replacement if you look at google, but may be a bit too much for a single project, which needs to maintain all this stuff.

i used owncloud and despite the other flaws, the missing incremental sync (which will not be added later) was the top argument. you cannot upload 100 mb each time you change a tiny bit.

Comment: Re:Drop owncloud (Score 1) 126

by allo (#48228721) Attached to: OwnCloud Dev Requests Removal From Ubuntu Repos Over Security Holes

It's not my code, i am only a user.
But in my experience, the developers are reacting quite good on "issues" on their github (see the repos of haiwen).
On the other hand, the owncloud devs tend to "i close this (still open) bug due to inactivity", when the inactivity is on their side, because they just need to fix the stuff with all information already provided.

Some people have a great ambition: to build something that will last, at least until they've finished building it.

Working...