Search found 35 matches

by philoctetes
Thu Feb 27, 2014 1:33 pm UTC
Forum: Mathematics
Topic: Axiomatic mathematics has no foundation
Replies: 158
Views: 35995

Re: Axiomatic mathematics has no foundation

I'm actually enjoying this discussion (for which I must greatly credit Forest Goose), which is why I feel kind of guilty at the following attempt to kill it (also, I'm going to be a bit of a dick about it): Treatid, let's give you a small case study. I'll present a small and simple proof taken from ...
by philoctetes
Sat Feb 15, 2014 1:15 pm UTC
Forum: Mathematics
Topic: quarkcosh1's math coincidences thread
Replies: 32
Views: 9321

Re: quarkcosh1's math coincidences thread

Bravo, fishfry!
by philoctetes
Sun Jan 05, 2014 2:08 pm UTC
Forum: Mathematics
Topic: Determinism and P=NP
Replies: 7
Views: 2650

Re: Determinism and P=NP

The Travelling Salesman Problem is a mathematical problem, and does not "reduce" to a physical problem (at least not in the sense you are referring to). In addition, I'll note that NP is actually more usefully defined without reference to determinism (see the verifier-based definition on W...
by philoctetes
Tue Dec 18, 2012 9:45 am UTC
Forum: Mathematics
Topic: Multi-dimensional Optimization
Replies: 1
Views: 1305

Re: Multi-dimensional Optimization

Well, considering the numbers, brute force seems simplest: say, 30c5 * 30 is a completely manageable number, it won't take more than a second to enumerate all possibilites. If you're closer to 100 in each collection you might want to consider something else.
by philoctetes
Mon Oct 29, 2012 12:27 pm UTC
Forum: Mathematics
Topic: Mean of standard deviations vs. global standard deviation
Replies: 0
Views: 1670

Mean of standard deviations vs. global standard deviation

Hello, This is a sort-of crosspost from math.stackexchange. Let's say I have a bunch of samples from a sequence of days, by week. In other words, I have \{x_{i,j} : i = 1..7,j=1..n\} , where i is the weekday and j is the week number. Can I get any meaningful info by examining the relation (ratio, su...
by philoctetes
Wed Jun 13, 2012 10:05 am UTC
Forum: Computer Science
Topic: Some questions about the exponential hierarchy
Replies: 5
Views: 4336

Re: Some questions about the exponential hierarchy

Wait, who is s/he?
by philoctetes
Sun Jun 03, 2012 12:08 pm UTC
Forum: Computer Science
Topic: Asymptotically-Optimal Algorithms to Decide NP Problems
Replies: 3
Views: 3022

Re: Asymptotically-Optimal Algorithms to Decide NP Problems

Seems like almost any of those we know would do, no? I will now wave my hands like I just don't care:
Say, for SAT, guess a satisfying assignment. Running time is linear, and any sublinear algorithm will fail by some application of the pigeonhole principle.
by philoctetes
Sun May 06, 2012 9:32 pm UTC
Forum: Computer Science
Topic: Turing Machine Enumeration
Replies: 5
Views: 8067

Re: Turing Machine Enumeration

Take an enumerator for all Turing machines with a specific lexicographical ordering. Then when reaching the k-th machine in this ordering, simply check all permutations of its states and verify that no permutation gives you any machine whose place in the ordering is in {1,...,k-1}. I'm not sure whet...
by philoctetes
Mon Apr 30, 2012 3:31 pm UTC
Forum: Mathematics
Topic: Base for Pi
Replies: 5
Views: 1901

Re: Base for Pi

Curses, foiled again!

Just you wait, Dason. Next time the sweet, sweet algorithms will be mine!
by philoctetes
Thu Mar 15, 2012 12:49 pm UTC
Forum: Computer Science
Topic: Orcle TM eh?
Replies: 5
Views: 3183

Re: Orcle TM eh?

Hail phlip, restorer of worlds!
Good answer. Elegant reduction.
by philoctetes
Mon Mar 05, 2012 10:40 am UTC
Forum: Computer Science
Topic: Another NP Complete thread
Replies: 27
Views: 8494

Re: Another NP Complete thread

Oh, well, while we're listing them... While we don't know where BPP or BQP stand in relation to P and NP, we know that BPP <= BQP. Connecting randomization in some sense, though, we also know IP = PSPACE, and also QIP = PSPACE from which we get QIP = IP.
by philoctetes
Mon Jan 30, 2012 3:53 pm UTC
Forum: Science
Topic: How can I obtain hard-to-get papers?
Replies: 14
Views: 2834

Re: How can I get hard to get papers?

I really don't think getting hard will help you get any papers.
by philoctetes
Sat Jan 28, 2012 5:02 pm UTC
Forum: Mathematics
Topic: Sorting elements of a rectangular array
Replies: 4
Views: 1893

Re: Sorting elements of a rectangular array

I'm feeling rather lazy at the moment, so I only skimmed the link, but isn't this radix sort?

EDIT: On review, I don't think it is. Sorry! Move along...
by philoctetes
Tue Jan 10, 2012 4:54 pm UTC
Forum: Mathematics
Topic: Are conversations considered markov chains?
Replies: 9
Views: 3622

Re: Are conversations considered markov chains?

At least three. Proof: this sentence.
by philoctetes
Thu Dec 01, 2011 11:16 am UTC
Forum: Computer Science
Topic: k-partite DAG question
Replies: 5
Views: 1586

Re: k-partite DAG question

I'm not interested in outputting all paths, Well, that's what your post said. Actually, it didn't say that. though, only in knowing if at least one path exists (for each pair of s,t vertices). For example, simply running All-Shortest-Paths (say, Floyd-Warshall) and printing all (s,t) pairs with les...
by philoctetes
Wed Nov 30, 2011 2:54 pm UTC
Forum: Computer Science
Topic: Determining equality of non-well-founded sets
Replies: 12
Views: 3092

Re: Determining equality of non-well-founded sets

My mistake, you're right.
by philoctetes
Wed Nov 30, 2011 12:31 pm UTC
Forum: Computer Science
Topic: Determining equality of non-well-founded sets
Replies: 12
Views: 3092

Re: Determining equality of non-well-founded sets

I may be looking wrong at your examples, but I don't see any way in which the two are different.

In the second example, taking A = B = {2,{2,{2,..} } } is no contradiction.Or if there's something wrong with that, why isn't the first example bad too?
by philoctetes
Wed Nov 30, 2011 8:54 am UTC
Forum: Computer Science
Topic: k-partite DAG question
Replies: 5
Views: 1586

Re: k-partite DAG question

I'm not interested in outputting all paths, though, only in knowing if at least one path exists (for each pair of s,t vertices). For example, simply running All-Shortest-Paths (say, Floyd-Warshall) and printing all (s,t) pairs with less than infinite paths would work. But that would be cubically pol...
by philoctetes
Tue Nov 29, 2011 11:04 am UTC
Forum: Computer Science
Topic: k-partite DAG question
Replies: 5
Views: 1586

k-partite DAG question

Hi, Is there a known algorithm which runs in close to linear time, which receives a k-partite directed graph and outputs all pairs (s,t) where s is a vertex in the 'first' part of the graph and t is a vertex in the 'k-th' part? EDIT: I wasn't specific enough. The assumption is that there are only ed...
by philoctetes
Fri Nov 18, 2011 6:58 pm UTC
Forum: Computer Science
Topic: Strongly connected directed graph
Replies: 8
Views: 3553

Re: Strongly connected directed graph

Hand-wavey attempt at an algorithmic proof: Choose some ordering of the nodes (v_1,...,v_n). Now build two trees: Tree 1: E_1 = empty set. For i=1 to n, add to E_1 all the outgoing edges of v_i such that they do not complete a cycle in E. Tree 2: same thing for ingoing edges. Then show that every ed...
by philoctetes
Thu Oct 20, 2011 9:13 pm UTC
Forum: Mathematics
Topic: Cantor's Diagonalization Proof
Replies: 314
Views: 19591

Re: Cantor's Diagonalization Proof

It's not as if one can actually list all the natural numbers I think perhaps what is confusing you is the "list" aspect of it. Remember that 'list' is shorthand for one-one correspondence. It doesn't have to be an iterative, one-after-the-other kind of matching. Take a simple example: if ...
by philoctetes
Fri Oct 07, 2011 8:30 am UTC
Forum: Computer Science
Topic: TMs, NTMs and QTMs [Quantum Computing]
Replies: 4
Views: 2976

Re: TMs, NTMs and QTMs [Quantum Computing]

Well, I'll preface by saying that IANAPhysicist, and don't even much remember of the Quantum Computing course I took.. I hope people will correct whatever errors I'll make. First off, when talking about the power of quantum computing, we don't use the TM model - we use the Circuit model (I could get...
by philoctetes
Wed Oct 05, 2011 9:06 am UTC
Forum: Computer Science
Topic: Question (Related to P=NP)
Replies: 20
Views: 4146

Re: Question (Related to P=NP)

Wait, what? I think I might be missing something here... Look at, say, the proof that SAT is NP-Complete. There the whole point of the reduction is that you get as input a description of the NTM M solving some problem in NP and input x for M, and create a (polynomial in the length of, etc.) formula ...
by philoctetes
Sun Aug 07, 2011 12:22 pm UTC
Forum: Science
Topic: Finity
Replies: 60
Views: 7711

Re: Finity

noses wrote: Also, if I were 'studying' 'philosophy' i would 'kill' myself. And i'd stringly recommend the same to anyone in that position.


And thus is the String Theory conspiracy unmasked!
by philoctetes
Fri Aug 05, 2011 2:46 pm UTC
Forum: Mathematics
Topic: Whole Number Solutions
Replies: 6
Views: 1286

Re: Whole Number Solutions

Obligatory quote:
19-year old Erdos, after finding a different proof for Bertrand's Postulate:

"Chebyshev proved it, and I proved it again:
there is always a prime between n and 2n".
by philoctetes
Thu Jun 16, 2011 8:18 am UTC
Forum: Mathematics
Topic: This is what bothers me about predicate logic
Replies: 15
Views: 3759

Re: This is what bothers me about predicate logic

For example lets take the predicate logic formula Rxy ... How many ways are there to translate that into english and how many words are there that don't work as values for x and y? Also don't say infinitely many because there are a finite number of words in the english language so this should have ...
by philoctetes
Thu May 12, 2011 4:41 pm UTC
Forum: Mathematics
Topic: Equation for Permutations of Game of Chess ?
Replies: 14
Views: 11504

Re: Equation for Permutations of Game of Chess ?

I find it hard to believe that a computer could brute force it - that wouldn't necessarily mean that we could solve chess, but I think it wouldn't be far from that. If we mean the same thing by 'brute force', i.e. not some sort of sophisticated counting, but actually tracking all possible movesets, ...
by philoctetes
Thu Apr 28, 2011 3:12 pm UTC
Forum: Mathematics
Topic: Special Numbers (i.e. pi, e, i, ect.)
Replies: 18
Views: 2824

Re: Special Numbers (i.e. pi, e, i, ect.)

Assuming what the OP means is, why did we choose the specific words "irrational,imaginary" to denote the concepts they are used for: 'Irrational' comes from 'ratio' rather than 'rational' - Irrational numbers are those which cannot be expressed as a ratio between two integers. And wikipedi...
by philoctetes
Mon Feb 14, 2011 6:24 pm UTC
Forum: Serious Business
Topic: Does God Exist?
Replies: 1390
Views: 126058

Re: Does God Exist?

Still, existence is a perfection unrelated to spelling


I bug to duffer, sir!
by philoctetes
Sun Dec 12, 2010 11:08 am UTC
Forum: Mathematics
Topic: Modern Cryptanalysis
Replies: 12
Views: 4164

Re: Modern Cryptanalysis

Without knowing a whole lot about the subject, I'd suggest reading http://en.wikipedia.org/wiki/Md5 , http://en.wikipedia.org/wiki/Hash_collision , http://en.wikipedia.org/wiki/Collision_attack and http://en.wikipedia.org/wiki/Cryptographic_hash_function . And basically, what heyitsguay said. I don'...
by philoctetes
Mon Nov 22, 2010 10:39 am UTC
Forum: Mathematics
Topic: Some short questions about computational complexity theory
Replies: 16
Views: 1963

Re: Some short questions about computational complexity theo

O(2 log n ) = O( n ) O(2 log (log n ) ) = O(log n ) (...) n is defined to be the size of the input, not log n . And in a prime checking algorithm it makes way more sense to define the input's size by its magnitude rather than by the number of digits. Think logically. Maybe also read some wi...
by philoctetes
Mon Nov 01, 2010 10:22 am UTC
Forum: Mathematics
Topic: My idea on why math is hard...
Replies: 28
Views: 4005

Re: My idea on why math is hard...

There's the famous von Neumann quote (I really love it):

"Young man, in mathematics you don't understand things, you just get used to them."
by philoctetes
Sat Oct 30, 2010 6:00 pm UTC
Forum: Mathematics
Topic: knapsack-like problem
Replies: 5
Views: 1265

Re: knapsack-like problem

Solving an LP restricted to integer solutions is indeed NP-hard. The best you can do, as nxcho says, is to be satisfied with a less-than-optimal solution: use the simplex method to solve the LP allowing any real solution between 0 and 1, and then round up to 1 those greater than one half, round down...
by philoctetes
Tue Oct 12, 2010 1:24 pm UTC
Forum: Computer Science
Topic: Turing Machine building
Replies: 1
Views: 1124

Re: Turing Machine building

Describe the set of strings you don't accept in a sentence.

Describe the set of strings you do accept in a sentence.

How would a computer program differentiate between these two sets?
by philoctetes
Thu Sep 02, 2010 1:37 pm UTC
Forum: Mathematics
Topic: Image
Replies: 8
Views: 1143

Re: Image

More intuitively perhaps: Imagine you have a raygun that teleports stuff. This is your function. So you walk around zapping people, because, well, what else are you gonna do? If you live in America (and your raygun only works there - it runs on bald eagles or something), the domain of your function ...

Go to advanced search