Mathematics - 2017-06-21 (page 8 of 11)

4:06 PM

That is sufficiently vague as to be useless.

lol

@Semiclassical D:

@MikeMiller Yeah I think what you say is sound.

Mike Miller

I think it requires some nonzero work to verify that the limit does cut in half

Details here, albeit geared for an implementation in R: joyofdata.de/blog/…

I'm a bit annoyed that the Wiki page for linear separability doesn't talk about the relevant algorithms.

4:10 PM

How about, we pose a related problem, which is simpler?

Consider a point tracing out an ellipse.

It apparently comes up in machine learning a lot...which, okay, sure

isn't algorithms more of a math thing anyways?

@SohamChowdhury How's life now? Doing any math?

If we are in the same plane as the ellipse,

we can figure out the eccentricity easily.

Algorithms is most definitely a part of the theoretical side of computer science.

4:11 PM

Simply from a ratio.

@BalarkaSen Aren't you schoolmates or something

I thought the aspect of algorithms which was CS is for things exclusive to CS such as list operations and other stuff like that. I didn't think geometric processes and solving equations was something that fell in there...

:/

That's a pretty narrow view of CS.

@Akiva neh

well no, I just meant that math already has had algorithms for hundreds of years...

4:12 PM

So how do you know each other, again?

so @balarka if you have 2 lines between 2 pairs of points that cross you can replace them with 2 other lines that don't cross whose total length is smaller than that of the $2$ you started with because of the triangular inequality. Since there is a finite number of ways to place $n$ lines between $2n$ points there must be one with the smallest total length and this can't have any crossings by the argument above

and what about algorithms for mixing chemicals a special way?

@AlessandroCodenotti HOLY SHIT

THAT'S GENIUS

Looks like I'll have to pre type and then post.

i mean I'm just saying it cannot be all algorithms.

4:13 PM

that was my reaction too when I read that argument @akiva

@TheDarkSide Yeah that happens sometimes

Didn't say it was. But computational complexity stuff, for instance, is a huge part of CS.

@AkivaWeinberger :P

$P=NP$ or $P\neq NP$

@Semiclassical i hope you don't mean the level of rates of increasing like the big number stuff simple art messes with.

4:14 PM

@Alessandro O_O

O_o

$P=NP$ when $N=1$ or $P=0$. Can I get my million dollars now?

o_O

actually, had anyone checked whether that P NP problem is undecidable?

mind = blown

@Secret the problem is that it is a question about the nature of thinking itself and it is ultimately subjective.

4:15 PM

I'm consistent and complete.

in the sense that i might find verification harder than obtaining the potential solution

...no, it is not. NP != P or NP = P are not subjective statements.

(Whether or not I can do arithmetic remains to be seen)

I thought we can check that by seeing if there's a map that can map it to the halting problem

that's some serious dark magic, I found it earlier on reddit, but there wasn't a source

4:16 PM

if such map exists, then P,NP problem will be undecidable

@Semiclassical it's a question about whether or not verifying a solution is easier than finding it. That's literally a question about human ability. XD

What the answer is, I have no idea. How it will ever be proven, I have no idea. But P and NP are well-defeined thing.

Bullshit.

This is fantastic, though. I am going to note this technique down somewhere.

P != NP is not a question about human abilities.

oh

4:17 PM

@Typhon That's the pop-math version. The real thing involves polynomial times and stuff

well then define "easier"

They just found a numerical invariant (total length) which the ultimate configuration minimizes.

"Polynomial time" is considered "easy"

@AkivaWeinberger oh so computer verification?

though that's not 100% accurate

4:17 PM

@BalarkaSen I think there is a somewhat similar proof of the Sylvester-Gallai theorem, but I haven't read it in ages so I might be wrong

Q: Proof that the halting problem is NP-hard?

8

(I apologize if this is the wrong site for this question, but given that there are many "not-hard-enough-for-CS-Theory" CS theory questions floating around here, I think that this might be a good fit. Please feel free to move this if it's inappropriate.) In this answer to a question about the d...

O whoops, halting problem is NP

What is Sylverster-Gallai again?

so it cannot really say anything about P,NP

@Secret Isn't halting problem undecidable??

I thought NP stuff were all decidable

@BalarkaSen given $n\ge 2$ points in the plane either they're all collinear or there is a line that contains only $2$ of them

4:19 PM

That's what I knew too about the halting problem, I however don't know much about the decidability of the different complexity classes

@Semiclassical true, but I was making the argument that an algorithm for finding a plane with certain qualities falls more into the math realm than the computing realm.Or at the very least,the algorithm itself isn't restricted purely to computers or only useful in the context of a computer.Not to say that people cannot use computers to study it.We have programs like matlab and mathematica for that sort of stuff,but I simply meant that it seems more like an application of CS than something part of it.

@Alessandro Ah, right, I remember this. I will try to rederive the proof for a few minutes (don't reveal, people)

I can't reveal what I don't remember

quora.com/…

and it seems to be even more complicated than I thought

I have a vague memory of a proof that derives a contradiction by finding a solution with a smaller area for something that was supposed to be minimal, but I forgot all the details...

4:21 PM

Oh, turns out undecidable and NP-hard overlap, but undecidable and NP don't

@Typhon defining computer science as "what PCs can do" is an exceptionally narrow view of CS

@Secret

ah I see

Also another weird question:

@Semiclassical Well would naturally presume that the center of computer science is computers and things relevant to software engineering and such. Not to say there aren't theoretical aspects, but to some degree there are parts more ingrained within the subject than things are merely studied because they serve as applications for working with things outside the realm of computer science.

4:23 PM

@AlessandroCodenotti To dissect that proof: You can think of it as, you start with a random arrangement of line segments between the things. At each stage, you undo a crossing. You want to show that this must terminate.

To do that, you utilize a monovariant: length.

it's just weird to me that a geometry problem falls directly in computer science, ok? Seems more like it would be a math problem. XD

Computer science is essentially part of math, I think

Let me put the point like this. In what sense is computer science a science?

(but that might be wrong)

@AkivaWeinberger yep

A: Is computer science a branch of mathematics?

4:25 PM

153

Theoretical computer science could certainly be considered a branch of mathematics. This branch of computer science deals with computers and computer programs as mathematical objects. Theoretical computer scientists could be described as computer scientists who know little about computers. Howev...

@AkivaWeinberger I would say partially so, but my point was that the problem doesn't seem to have a direct application in CS. It seems more like something CS could be used for to help solve a geometry problem.

For a longer-form version of the mindset I'm pointing towards: cs.mtu.edu/~john/jenning.pdf

"However, when people say "computer science" they usually include many things which would not be considered mathematics, for instance computer architecture, specific programming languages, etc."

tbf, I did say that the two subjects "intersect"

yes, and the geometry problem we're talking about lies in that intersection :/

In any case, complexity theory $\subset$ theoretical computer science $\stackrel?\subset$ math

going by that answer

4:27 PM

@Semiclassical fair point. I guess the computational analysis is CS and the geometry itself is math.

We knew that in topology there are 4 different types of sets: Open, closed, clopen and neither. Therefore unlike a door, if it is not open, it is not necessary it is closed

Now, in classical logic, we have a proposition $A$ and its negation $-A$ . The law of excluded middle says these are the only two truth values we can have

Now my question is: Given a mathematical object with entities $A$ and its opposite $-A$. How can we show that there does/does not exists an object $C$ such that $C\neq A$ and $C\neq -A$. Putting this question using topology as an example, if $A$ is an open set, then …

The way I'd put it is that the concepts involved in posing the problem are not computational in nature.

@Secret I'm not sure I understand that question, but uncomputable is defined as "not computable"

@Semiclassical that's probably a good way to phrase it and also just asking for such a line isn't really CS since well.... geometry. XD

and closed is not defined as "not open"

4:28 PM

Well, keep in mind that there are two things:

"Does such a line exist?"

That, I would agree, is not computational.

"How do I find such a line?" That is certainly computational.

i know what you're getting at, but by that reasoning, finding the "foot" of a point to a line is a cs problem...?

The word 'find' is the key one for me.

How do I find such a line with the least amount of resources, really

Sure. It's just a really trivial one.

...

4:30 PM

The hardness of the task isn't what makes it computational. It's that it can be posed as a computation in the first place.

head explodes

I mean, heck, binary addition

That's an algorithm.

@Semiclassical addition is computation

damnit!

Scanners (1981) US trailer

►

The only real way to get a feel for the subject is to actually read stuff in it, or to do stuff in it

Talking about it won't give much insight

4:31 PM

This has become a bit of a meme for me

@AkivaWeinberger And work with people who know it, preferably

@AkivaWeinberger not sure who you're talking to?

You

Well, I am wondering in general how we can show that "a third option" exists or don't exists. For example. why we cannot have a function that is neither computable nor uncomputable

O wait. If we have $-(P \wedge -P)$, then $-(P \wedge -P)=-P \vee P$ so that means it is either computable or uncomputable...

Here's another aspect of this.

4:32 PM

…Yeah @Secret

guys. the browser is saying this page is not secure/safe

something about images

Weird

Maybe the Youtube link is making it unhappy

I think that scanners trailer made the browser think it was getting scanned.

Nothing to do with the weird polyhedron I posted an hour ago, I hope

4:33 PM

...then that's either a really smart or a really dumb browser

@Semiclassical or the setup to a really bad joke.

Browser got it's head exploded

The scanning experience is usually not a pleasant one after all

Suppose I look at a set of points, and I want to find a line to divide it up into two subsets. Setting aside how I might find it systematically, the human brain is pretty good at finding a solution to the problem.

and $-P \wedge -(-P) = -P \wedge P$ is a contradiction, thus classical logic said such functions cannot exist

How does the brain do that?

4:35 PM

@Semiclassical Even when it's lots of densely packed points?

Eh. If there's not too many points?

Perhaps

My point is more that, to the extent that humans succeed at finding such lines, they tend to do so pretty quickly

@AlessandroCodenotti What if there's an infinite amount of points, I wonder?

I suspect we did that by focusing at the most empty channel between the set of points, then drew a line there

4:37 PM

Under certain conditions to make it more plausible

More generally, the human brain is good at classifying images.

Like, say they're all isolated

@Semiclassical So… throw a neural net at it?

note how whenever we were asked to do that problem, our eyes tend to focus on the empty spaces between the points

I've seen that approach to smoke simulation, by the way.

Which, beforehand, involved (I think) complicated differential equations and was computationally expensive

It's not perfect but it's pretty good

I wonder how will computer algorithms detect those empty spaces?

4:38 PM

@Semiclassical Umm... The problem is to divide a set of points into two symmetrical images. That's not a trivial problem. At the very least, it requires some math in terms of averaging points.

distracted for now

@Alessandro S-G is proving to be harder than I thought. Maybe I won't find a proof after all :P

chances are slim to none that I'll get into full time at UWO

I need a textbook for geometric combinatorics, man. This stuff is great fun.

An Optical Poem (1938) - Classic Short Film

►

4:39 PM

@AkivaWeinberger well there are symmetric functions to just look for the point or line of symmetry?

Wait a second.... P = NP should always be P >= NP as part of finding the solution includes verification.

@dodsy how come?

That tune though

always reminds of tom & jerry

@Zee they said my application came in too late

I've been waiting 6 weeks

MGM logo enriches it

@Typhon Wrong way around. $P\subseteq NP$.

But that is the right reason.

4:42 PM

@AkivaWeinberger P is finding the solution, right?

NP is validation?

Yeah

So if it's in P, it's in NP

@dodsy well you can always transfer next semester

so... in order to find a solution you must during the process validate

@Zee :{

therefore the time to find a solution is longer than validating it

Erik Satie - Gymnopédie No.1

4:43 PM

►

@Dodsy it will be ok man, I went to community college before I transferred into a good uni

yeah..

Well they said I could do part time

@Typhon So if it's easy to solve (including validation), then it's easy to validate.

but I'd need to pay another 50 bucks.

Do part time, just take the math classes, this way you won't slow down at all

4:45 PM

@AkivaWeinberger P = NP asks for a relationship between the time to validate and the time to obtain a solution.

im saying that the time to find a solution is the time to validate along with some other stuff as validation is a requirement of obtaining a solution

I'd have to take 3 courses

@AlessandroCodenotti Here's a problem I don't know the answer to. You have finitely many points in 3-space. Is there a direction along which there's at least $2$ maxima and at least $2$ minima?

only 2 math classes offered per semester

so I'd need to do physics or compsci.

Im gonna go for a drive.

@Typhon To be clear, both P and NP are sets of problems. They're not amounts of time.

They're not numbers.

@Dodsy this sounds like a scam to me.

@AkivaWeinberger they are not the general times to compute some.... thing?

4:47 PM

No. P is the set of problems that can be solved in polynomial time ("quickly")

NP is the other one

not polynomial

NP is the set of problems that can be shown to be correct in polynomial time ("quickly") when provided with a token

oooh

@Typhon Nondeterministic Polynomial time

is what it stands for

ooooh

so it's not "time to solve" and "time to verify"

4:48 PM

No

ok now I can see why the problem is more tricky

Yeah

Oh, and technically, they're all meant to be sets of yes/no problems

And there's some variable in each problem

Lol people thought I was a bot...

@Dodsy Here's what I'm thinking happened. Someone either screwed up and lost your application or misplaced it or they basically pocketed it so they wouldn't have to admit you. Then, they can say "well it is too late to go elsewhere so you have to take part time or not got to college. Btw, it will cost you more in the long run to do part time, because then you're not eligible for scholarships!"

@Zee you were posting literal gibberish.

Yes, people do that you know

4:51 PM

Consider the Traveling Salesman problem. Here's the yes/no version: Inputs: A set of points (and distances between the points), and a number.

you misunderstand, you were spontaneously posting things completely unrelated to the conversation as if you were responding to some other conversation.

Output: Yes if there's a path through all of the points with total length less than the number, no otherwise

(I hope I'm doing this correctly)

(In fact, let me double-check)

@AkivaWeinberger the what

@Typhon paper is not made from wood

Then zee is ok, cause I post a lot more gibberish than anyone else here (except spammers and trolls)

4:53 PM

-_-

I have posts that are known to direct at no one

or more accurately, the audience is nonlocal

Lol people thought I was a bot

Glass is actually are from sand

@Secret except in this case it was annoying people.

@Typhon OK, I got it correctly.

So, the Traveling Salesman Problem is,

@AkivaWeinberger i still don't know what the travelling salesman problem is

4:55 PM

I was describing it

The Traveling Salesman Problem is,

and I got the question now about p = NP

It's about being a traveling salesman, just imagine that

given a bunch of points and a number $L$,

i see what it is asking

does there exist a route through all the points with total length less than $L$?

4:55 PM

@AkivaWeinberger I'm not sure what you mean

So, this is NP, because:

If the answer is "yes,"

then you can just provide the route.

And it's "easy" (polynomial time) to just sum the lengths of the parts of the route and show that it's less than $L$.

@Zee You're not a bot, you're just a pessimist :P

However, it's not known whether it's in $P$.

(= realist, i know)

Nobody has found any "quick" algorithm that always solves it correctly.

In fact, it's in a special class called $NP$-complete. What that means is that it's essentially among the hardest things in $NP$. If it's in $P$, then everything in $NP$ is in $P$.

4:58 PM

@Semiclassical you know something is wrong when people on a math chat start calling you a pessimist

Meaning that, if it's in $P$, then $P=NP$.

@Zee this isn't a math chat

I was going to post a paragraph about mathematical coincidence and bypassing phenomenon but this discussion is ongoing and potentially interested, thus I will leave that for the downtime

@Typhon The title of the room notwithstanding...

@Semiclassical it's a stock exchange chat