## Search found 35 matches

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 ...
Sat Feb 15, 2014 1:15 pm UTC
Forum: Mathematics
Replies: 32
Views: 9321

### Re: quarkcosh1's math coincidences thread

Bravo, fishfry!
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...
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.
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...
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?
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.
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...
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!
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!
Mon Mar 05, 2012 10:40 am UTC
Forum: Computer Science
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.
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.
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...
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.
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...
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.
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?
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...
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...
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...
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 ...
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...
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 ...
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!
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".
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 ...
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, ...
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...
Mon Feb 14, 2011 6:24 pm UTC
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!
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'...
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...
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."
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...
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?
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 ...