## 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
- Topic: quarkcosh1's math coincidences thread
- 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.

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!

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!

Good answer. Elegant reduction.

Good answer. Elegant reduction.

- 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.

- 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...

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?

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 ...

### 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".

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
- 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!

- 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."

"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?

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 ...